兩兩交換連結串列中的節點

      給定 1->2->3->4, 你應該返回 2->1->4->3

方法1：迭代

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next)   return head;
        ListNode* dummy = new ListNode(-1),*pre = dummy;
        dummy->next = head;
        while(pre->next && pre->next->next){
            ListNode*t = pre->next->next;
            pre->next->next = t->next;
            t->next = pre->next;
            pre->next = t;
            pre = t->next;
        }
        return dummy->next;
    }
};

dummy是新連結串列的頭指標，該遍歷過程需要用到2個指標，pre和t。pre指向當前需要交換兩個節點的前一個節點，t指向需要交換兩個節點中後面的一個節點。每次交換完成之後對pre進行移動

方法2：遞迴

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next)   return head;
        ListNode* first = head;
        ListNode* second = head->next;
        head = second;
        first->next = swapPairs(second->next);
        second->next = first;
        return head;
    }
};

該過程用到了2個節點，fisrt指向需要交換的兩個節點中的前一個節點，second則指向後面的一個節點。每次把head賦值second，先隊員first->next賦值，再對second->next賦值。迭代的思想也是先對first進行操作。遞迴需要額外的O(N)的棧空間

 

參考地址：https://blog.csdn.net/qq_34269988/article/details/89492526