Swap Nodes in Pairs

Given a linked list, swap every two adjacent nodes and return its head.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3. Note:

Your algorithm should use only constant extra space. You may not modify the values in the list's nodes, only nodes itself may be changed.

Solution: Using Recursion

We start swaping pairs from the tail of the list. The tricky part is to return the new head.

    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode *node = swapPairs(head->next->next);
        ListNode *newHead = head->next;
        head->next->next = head;
        head->next = node;
        return newHead;
    }

Solution: Modify the address

    ListNode* swapPairs(ListNode* head) {
        ListNode **ptr=&head;
        ListNode *first, *second;
        while ((first=*ptr) and (second=first->next)) {
            first->next=second->next;
            second->next=first;
            *ptr=second;
            ptr=&(first->next);
        } 
        return head;
    }

Solution: Modify the values in each node

If we can modify the values in each node, this will become quite easy to solve.

    ListNode * swapPairs(ListNode * head) {
        // write your code here
        ListNode *cur = head;
        while (cur && cur->next) {
            int temp = cur->val;
            cur->val = cur->next->val;
            cur->next->val = temp;
            cur = cur->next->next;
        }
        return head;
    }