[LeetCode] 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.

思路：

和reverse linked list很像，只不过每次reverse两个节点。同样要考虑奇偶数长度的情况。并且由于头节点会变动，dummy节点又能派上用场了。

奇数：

1->2->3

2->1->3

偶数

1->2->3->4

2->1->4->3

要constant space所以不能用递归。那就用一个指针p边扫描边reverse。用一个子函数来完成reverse pair并接回原链表的操作，返回值为pair的尾部，也就是p下一个移动位置。

D->1->2->3->4

 |
p          

D->2->1->3->4
             |

             r = swapNodes(p->next)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

class Solution { public: ListNode *swapPairs(ListNode *head) { ListNode *dummy = new ListNode(0); dummy->next = head; head = dummy; while(head) head = swapNodes(head->next); head = dummy->next; delete dummy; return head; } ListNode *swapNodes(ListNode *&head) { if(!head || !head->next) return NULL; ListNode *tail = head; ListNode *nextHead = head->next->next; head = head->next; head->next = tail; tail->next = nextHead; return tail; } };

不用子程序也可以用三指针扫描来完成：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

class Solution { public: ListNode *swapPairs(ListNode *head) { ListNode *dummy = new ListNode(0); dummy->next = head; ListNode *prev = dummy, *cur = head; while(cur && cur->next) { prev->next = cur->next; cur->next = cur->next->next; prev->next->next = cur; prev = cur; cur = cur->next; } return dummy->next; } };