Swap Nodes in Pairs

The problem

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

Function: def swapPairs(head):

Example input (a JSON list of arguments): [[1, 2, 3, 4]]
Expected output: [2, 1, 4, 3]

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. Keep a predecessor pointer before each pair and reconnect the two nodes in reversed order.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def swapPairs(head):
    dummy=ListNode(0,head);prev=dummy
    while prev.next and prev.next.next:
        a=prev.next;b=a.next;a.next=b.next;b.next=a;prev.next=b;prev=a
    return dummy.next

Why it works

Keep a predecessor pointer before each pair and reconnect the two nodes in reversed order. Advance to the original first node after swapping. Values are not exchanged; the links are.

Complexity: O(n) time / O(1) extra space.

Time: O(n) time · Space: O(1) extra space