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.
Solution: 1. Iterative solution with constant space.
2. Recursive solution with O(n) space (for practice).
1 class Solution {
2 public:
3 ListNode *swapPairs(ListNode *head) {
4 ListNode dummy(0);
5 ListNode* cur = &dummy;
6 cur->next = head;
7 while(cur->next && cur->next->next) {
8 ListNode* move = cur->next->next;
9 cur->next->next = move->next;
10 move->next = cur->next;
11 cur->next = move;
12 cur = move->next;
13 }
14 return dummy.next;
15 }
16 };