Swap Nodes 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.

https://leetcode.com/problems/swap-nodes-in-pairs/

Discussion

coding based on a real case. 循环里的code不要从第一组写，以一个普通的组写，前一组的第一个要指向当前组的第二个，所以需要前一组的信息。

Solution

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy = ListNode(-1);
        dummy.next = head;
        ListNode *curr = head;
        ListNode *nt;
        ListNode *savedCurr = &dummy;//有个dummy就不用考虑头是哪个了
        while(curr) {
            if(curr->next == NULL) break;
            nt = curr->next; 
            savedCurr->next = nt; //前一组的头指向当前组的第二个
            curr->next = nt->next;
            nt->next = curr;
            savedCurr = curr;//保存当前组的头供下次使用
            curr = curr->next;//总是在最后move current
        }
        return dummy.next;
    }
};

再来个优雅的递归~

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

ListNode* swapPairs(ListNode* head) {
        ListNode **p = &head;

        while (*p && (*p)->next) {
            ListNode *t = (*p)->next;

            (*p)->next = t->next;
            t->next = *p;
            *p = t;

            p = &(*p)->next->next;
        }

        return head;
    }