Swap Nodes In Pairs

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Input: head = []
Output: []

Input: head = [1]
Output: [1]

Solution

Intuition

The trick to this question is to use 3 pointers to swap. Let's say if we have the following a, b and c pointer:

This question we need to make 2-1-4-3

We can see a rule that:

b -> a
a -> c.next if c.next exists else c

As a result we can have

After that, we just need to move a to c and start the previous steps

b -> a
a -> c.next if c.next exists else c

Now we have this:

Implementation

class App:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if (not head or not head.next): return head

        newHead = head.next

        a = head
        b = head.next
        c = head.next.next

        while (a and b):
            a.next = c if c is None or c.next is None else c.next
            b.next = a

            a = c
            b = a.next if a else None
            c = b.next if b else None

        return newHead

Time complexity: $O(n)$
Space complexity: $O(1)$