leetcode 24: swap node in pairs

Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

Linklist 除了用slow, fast 算距离之外另一类题，利用recursion来对链表进行reverse,或者整个链表有规律地swap nodes. 对于这类利用recursion的题目，可以将整个链表看成是两个部分，一个是head sample,另一部分是subproblem, 对subproblem利用递归function进行处理之后，对head sample进行正常处理，reverse或者swap或者其他操作，然后return回结果的头结点。

class Solution {
public:
//use recursion  to solve
    ListNode* swapPairs(ListNode* head) {
        //sanity check
        if (head == NULL || head->next == NULL) return head;
        ListNode* next = head->next;
        ListNode* nnext = next->next;
        ListNode* newhead = swapPairs(nnext);
        next->next = head;
        head->next = newhead;
        return next;
    }
};
time complexity: O(n)
space complexity: O(n)

M2: iterative 的方法
如果用循环来做这一题，要注意指针变换的过程，因为head会改变，利用dummy来简化corner cases。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* pre = dummy;
        ListNode* cur = head;
        while (cur && cur->next) {
            ListNode* nnext = cur->next->next;
            pre->next = cur->next;
            cur->next->next = cur;
            cur->next = nnext;
            pre = cur;
            cur = nnext;
        }
        return dummy->next;
    }
};
space complexity: O(1)

dummy node 的使用： 如果dummy node是用来形成一个新的linklist, 那么不需要一开始就把dummy node 和 linklist 连起来，如果是对一条linklist进行操作，并且linklist的头会改变，也可以用dummy node 来做， 此时dummy node 要把Linklist连接起来，往往是利用pre指针指向该dummy node进行后面的操作。