24 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.

Solution:

/**
 * 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) {
        if ( head == NULL ) return head;
        if ( head->next == NULL ) return head;
        ListNode *dummy = new ListNode(0);
        ListNode *p1 = head, *p2 = p1->next, *p = dummy;
        while ( true ) {
            ListNode *tmp1 = p2->next;
            p->next = p2;
            p2->next = p1;
            p1->next = NULL;
            p = p1;
            p1 = tmp1;
            if ( p1 == NULL ) break;
            p2 = p1->next;
            // p->next = p1 takes special care of linked list with odd number nodes
            if ( p2 == NULL ) { p->next = p1; break; }
        }
        return dummy->next;
    }
};

Note:
Remember to use simple drawings to facilitate the manipulation of pointers!

recursive solution

/**
 * 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) {
        if ( head == NULL or head->next == NULL ) return head;
        ListNode* prev = head, *p = head->next, *next = p->next;
        p->next = prev;
        prev->next = swapPairs(next);
        return p;
    }
};