24. Swap Nodes in Pairs

Given 1->2->3->4, you should return the list as 2->1->4->3.

思路：

举个例子

1->2->3->4->5->6->7->8->9->10

step1 : prev = head, head = head->next
step2: away = head->next->next, neighbor = head-> next
step3: reverse 1-> 2 to 1<-2, cut 2->3, connect 1->4
step4: prev = neighbor, head = away, away = head -> next->next, neighbor = head->next

篮子王： https://www.youtube.com/watch?v=f45_eF1gmn8

方法1: iterative

建立一个prev node，每次以prev node为轴心发起swap(prev->next, prev->next->next)，完成后向前推进两个node，直至遇到nullptr。写法一将swap单独包装成一个函数，在主函数里处理prev和cur的递进，比较清晰。如果都写在一起就是二刷的写法。

易错点：

1. swap faunction里交接的顺序
2. 最后应该返回newHead->next，此时head已经被更改，直接return head会丢掉第一个node
3. 注意循环判空条件：while( cur && cur -> next) : 如果有落单的node也可以停下了
   

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head) return nullptr;
        ListNode* newHead = new ListNode(-1);
        newHead -> next = head;
        ListNode* prev = newHead;
        while (prev->next && prev->next->next){
            swap(prev);
            prev = prev -> next -> next;
        }
        return newHead->next;
        
    }        
        void swap(ListNode* prev){
            ListNode* dummy = prev->next;
            prev->next = dummy ->next;
            dummy -> next = dummy->next->next;
            prev ->next ->next = dummy;
            return;
        }
    
};

// 二刷：
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head) return nullptr;
        ListNode* newHead = new ListNode(-1);
        newHead -> next = head;
        ListNode* cur = head, *prev = newHead;
        
        while (cur && cur -> next) {
            ListNode* tmp = cur -> next;
            cur -> next = tmp -> next;
            tmp -> next = prev -> next;
            prev -> next = tmp;
            prev = cur;
            cur = cur -> next;
        }
        return newHead -> next;
    }
};

方法2: recursion

grandyang : http://www.cnblogs.com/grandyang/p/4441680.html
思路： 假设每次swapPairs的返还值已经把子链swap好，并且返还头节点，每一步的递归中只需要将head 和head -> next swap好：链接子链到head，将head和head->next之间的链反转，然后返回head->next到上一层函数

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