成對交換節點


難度級別
經常問 亞馬遜 Microsoft微軟 月蛙實驗室
鍊錶

在成對交換節點問題中,我們給出了一個 鍊錶 由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

參考