# 24 - Swap Nodes in Pairs

解法一 - Recursion 解法

這題因為是兩個兩個 node swap，所以直覺就會想到要用 recursion 來解 => 先 swap 完兩個，然後再把剩下的 list 當作一個子問題，重新呼叫一次 function。

實作出來的程式碼如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next) return head;

        ListNode* newHead = head->next;
        head->next = newHead->next;
        newHead->next = head;

        head->next = swapPairs(head->next);

        return newHead;
    }
};

解法二 - Iterative 解法

這題除了用 recursive 解法，直覺上也是可用 iterative 的解法。

主要的問題就是要控制好每次 swap 完一對的起終點：

如果我們用瀑布式的思考方法，腦袋會很容易錯亂，因為目標狀態 (2->1->3->4->NULL) 跟初始狀態 (1->2->3->4->NULL) 差很多，我們需要注意的東西有：

1. 2 得是新的 head

2. 2->next 要更新成 1

3. 1->next 要更新成 3

4. 下次 iteration 開始， head 要指向 3

一個可以幫助我們寫出對的迴圈的方法是，就是清楚地寫下目標狀態和起始狀態：

起始

0(dummy, node)->1(head)->2->3->4->NULL

目標

0(dummy)->2->1(node)->3(head)->4->NULL

然後就可以根據這兩個狀態來寫程式。

另外要注意最後的 NULL，所以記得檢查 (head && head->next)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next) return head;

        // Setup
        ListNode *dummy = new ListNode(0), *node;
        node = dummy;
        dummy->next = head;

        // Swap nodes
        while (head && head->next) {
            ListNode *nxt = head->next;
            head->next = nxt->next;
            nxt->next = head;
            node->next = nxt;
            node = head;
            head = node->next;
        }

        return dummy->next;
    }
};