成对交换节点


难度级别 中等
经常问 亚马逊 微软 月蛙实验室
链表

在成对交换节点问题中,我们给出了一个 链表 由n个节点组成。 考虑从0开始的索引,将每个节点交换为偶数索引,并将它与奇数index()处的右侧相邻节点交换。

成对交换节点

使用案列

输入: 1-> 2-> 3-> 4-> NULL

输出: 2-> 1-> 4-> 3-> NULL

输入: 1->2->3->4->5->6->7->NULL

输出: 2->1->4->3->6->5->7->NULL

迭代法

算法

  1. 创建一个具有整数变量的类Node来存储数据,并使用Node类型的Pointer作为其公共成员。
  2. 之后,创建一个函数以将数据推入节点内部并形成一个链表。
  3. 同样,创建函数以交换给定链表的节点,该节点接受链表的头作为参数。
  4. 创建一个临时的Node类型指针,并将其头存储在其中。
  5. 在临时节点指针不为空且下一个临时节点指针不为空时进行遍历。 将临时节点指针的数据与下一个临时节点指针的数据交换。 将临时节点指针更新为临时节点指针的下一个。
  6. 当head不等于NULL时再次遍历。 打印磁头的数据,并将磁头更新为下一磁头。

时间复杂度: O(N)

辅助空间: O(1)

C ++程序成对交换节点

#include <bits/stdc++.h> 
using namespace std; 
  
class Node{ 
public: 
    int data; 
    Node* next; 
}; 
  
void Swap(Node* head){ 
    Node* temp = head; 
  
    while((temp != NULL) && (temp->next != NULL)){ 
        swap(temp->data, temp->next->data); 
  
        temp = temp->next->next; 
    } 
    
    while (head != NULL) { 
        cout<<head->data<<"->"; 
        head = head->next; 
    }
    cout<<"NULL";
} 
  
void push(Node** head_ref, int new_data){ 
    
    Node* new_node = new Node(); 
  
    new_node->data = new_data; 
  
    new_node->next = (*head_ref); 
  
    (*head_ref) = new_node; 
} 
  
int main(){ 
    Node* start = NULL;
    
    push(&start, 7);
    push(&start, 6);
    push(&start, 5); 
    push(&start, 4); 
    push(&start, 3); 
    push(&start, 2); 
    push(&start, 1); 
  
    Swap(start); 
  
    return 0; 
}
2->1->4->3->6->5->7->NULL

Java程序成对交换节点

class List{ 
    Node head;  
  
    class Node{ 
        int data; 
        Node next; 
        Node(int d){ 
            data = d; 
            next = null; 
        } 
    } 
  
    void Swap(){ 
        Node temp = head; 
  
        while((temp != null) && (temp.next != null)){ 
  
            int k = temp.data; 
            temp.data = temp.next.data; 
            temp.next.data = k; 
            temp = temp.next.next; 
        } 
        
        while(head != null) { 
            System.out.print(head.data + "->"); 
            head = head.next; 
        } 
        System.out.print("NULL");
    } 
  
    public void push(int new_data){ 
        Node new_node = new Node(new_data); 
  
        new_node.next = head; 
  
        head = new_node; 
    } 
  
    public static void main(String args[]){ 
        List l = new List(); 
  
        l.push(7);
        l.push(6);
        l.push(5); 
        l.push(4); 
        l.push(3); 
        l.push(2); 
        l.push(1); 
  
        l.Swap(); 
    } 
}
2->1->4->3->6->5->7->NULL

递归方法

算法

  1. 创建一个具有整数变量的类Node来存储数据,并使用Node类型的Pointer作为其公共成员。
  2. 之后,创建一个函数以将数据推入节点内部并形成一个链表。
  3. 同样,创建函数以交换给定链表的节点,该节点接受链表的头作为参数。
  4. 创建一个临时的Node类型指针,并将其头存储在其中。
  5. 如果临时节点类型指针不等于NULL,并且下一临时节点类型指针不等于NULL,则将临时节点指针的数据与临时节点指针的下一数据交换。
  6. 将临时节点指针更新为临时节点指针的下一个。 使用更新的临时节点类型指针对函数本身进行递归调用。
  7. 头部不等于NULL时遍历。 打印磁头的数据,并将磁头更新为下一磁头。

时间复杂度: O(N)

辅助空间: O(1)

C ++程序成对交换节点

#include <bits/stdc++.h> 
using namespace std; 
  
class Node{ 
public: 
    int data; 
    Node* next; 
}; 
  
void Swap(Node* head){ 
    Node* temp = head; 
  
    if((temp != NULL) && (temp->next != NULL)){ 
        swap(temp->data, temp->next->data); 
  
        temp = temp->next->next; 
        Swap(temp);
    } 
} 

void print(Node* head){
    while(head != NULL) { 
        cout<<head->data<<"->"; 
        head = head->next; 
    }
    cout<<"NULL";
}
  
void push(Node** head_ref, int new_data){ 
    
    Node* new_node = new Node(); 
  
    new_node->data = new_data; 
  
    new_node->next = (*head_ref); 
  
    (*head_ref) = new_node; 
} 
  
int main(){ 
    Node* start = NULL;
    
    push(&start, 7);
    push(&start, 6);
    push(&start, 5); 
    push(&start, 4); 
    push(&start, 3); 
    push(&start, 2); 
    push(&start, 1); 
  
    Swap(start); 
    
    print(start);
  
    return 0; 
}
2->1->4->3->6->5->7->NULL

Java程序成对交换节点

class List{ 
    Node head,start;  
  
    class Node{ 
        int data; 
        Node next; 
        Node(int d){ 
            data = d; 
            next = null; 
        } 
    } 
  
    void Swap(){ 
        Node temp = head; 
  
        if((temp != null) && (temp.next != null)){ 
  
            int k = temp.data; 
            temp.data = temp.next.data; 
            temp.next.data = k; 
            temp = temp.next.next;
            head = temp;
            Swap();
        } 
        
        while(start != null) { 
            System.out.print(start.data + "->"); 
            start = start.next; 
        } 
    } 
  
    public void push(int new_data){ 
        Node new_node = new Node(new_data); 
  
        new_node.next = head; 
  
        head = new_node; 
        start = head;
    } 
  
    public static void main(String args[]){ 
        List l = new List(); 
  
        l.push(7);
        l.push(6);
        l.push(5); 
        l.push(4); 
        l.push(3); 
        l.push(2); 
        l.push(1); 
  
        l.Swap(); 
        System.out.print("NULL");
    } 
}
2->1->4->3->6->5->7->NULL

參考資料