Problem:

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:

//recursive solution
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode* next = head->next;
        head->next = swapPairs(head->next->next); //important
        next->next = head;
        head = next; 
        return head;      
    }
};

// copy
// iterative solution with dummy node
ListNode *swapPairs(ListNode *head) {
    ListNode *dummy = new ListNode(0), *node;
    node = dummy;
    dummy->next = head;
    while (head && head->next) {
        ListNode *nxt = head->next;
        head->next = nxt->next;
        nxt->next = head;
        node->next = nxt;
        node = head;
        head = node->next;
    }
    return dummy->next;
}

LeetCode Discussion

Memo:

Study dummy node.

Recursion need to give some implementation only once, otherwise it will be redundant.

//first version of my recursion code
//works but redundant
ListNode* swapPairs(ListNode* head) {
    if (head == NULL || head->next == NULL) return head;
    if (head->next->next == NULL) //this part is unnecessary,think why
    {
        ListNode* next = head->next;
        next->next = head;
        head->next = NULL;
        head = next;
    }
    else
    {
        ListNode* next = head->next;
        head->next = swapPairs(head->next->next); //important
        next->next = head;
        head = next;
    }
    return head;
}