2013.12.7 01:54

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:

　　This kind of problem is designed just to make some trouble for you, and the interviewer must be very glad watching you getting into a bloody mess with the code. So let's first write down the process in language description:

　　　　1. use two pointers $p1/$p2 pointing to the first/second node in each pair.

　　　　2. change the $next pointers of p1 and p2

　　　　3. swap $p1 and $p2, make sure $p1 is still before $p2.

　　　　4. record current $p2 as the parent pointer $par, which will be used in the next pair.

　　　　5. move both $p1 and $p2 forward by two steps, don't forget to check for nullptr.

　　　　6. {do the swapping for the next pair}, and point $par->next to $p1

　　Time complexiy is O(n), space complexity is O(1). The real problem is whether you can write the code nice and clean. Try to be careful and patient.

Accepted code:

// This problem is tricky, 3WA/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode *swapPairs(ListNode *head) {        // IMPORTANT: Please reset any member data you declared, as        // the same Solution instance will be reused for each test case.        ListNode *p1 = nullptr, *p2 = nullptr;                if(head == nullptr){            return head;        }                p1 = head;        p2 = head->next;        if(p2 == nullptr){            return p1;        }                bool first_swap = true;        ListNode *tmp, *par;        ListNode *root;                par = new ListNode(0);        root = par;        par->next = p1;        while(true){            p1->next = p2->next;            p2->next = p1;                        tmp = p1;            p1 = p2;            p2 = tmp;                        par->next = p1;            par = p2;                        if(first_swap){                head = p1;                first_swap = false;            }                        p1 = p1->next;            p2 = p1->next;            if(p2 == nullptr){                break;            }                        p1 = p1->next;            p2 = p1->next;            if(p2 == nullptr){                break;            }        }                delete root;        root = nullptr;        return head;    }};