24. Swap Nodes in Pairs

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

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example:

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

// Iteration
ListNode* swapPairs(ListNode* head) { // time: O(n); space: O(1)
    ListNode *dummy = new ListNode(-1);
    dummy->next = head;
    ListNode *pre = dummy, *cur = head, *nex = nullptr;
    while (cur && cur->next) {
        nex = cur->next;
        cur->next = nex->next;
        nex->next = cur;
        pre->next = nex;
        pre = cur;
        cur = cur->next;
    }
    ListNode *res = dummy->next;
    delete dummy;
    return res;
}

// Iteration
ListNode* swapPairs(ListNode* head) { // time: O(n); space: O(1)
    ListNode* dummy = new ListNode(-1);
    ListNode *pre = dummy;
    pre->next = head;
    while (pre->next && pre->next->next) {
        ListNode *t = pre->next->next;
        pre->next->next = t->next;
        t->next = pre->next;
        pre->next = t;
        pre = t->next;
    }
    ListNode* res = dummy->next;
    delete dummy;
    return res;
}

// Recursion
ListNode* swapPairs(ListNode* head) { // time: O(n); space: O(n)
    if (!head || !head->next) return head;
    ListNode *n = head->next;
    head->next = swapPairs(n->next);
    n->next = head;
    return n;
}