Problem statement

https://leetcode.com/problems/swap-nodes-in-pairs/

Solution

As with a lot of other linked lists, it is good idea to add dummy node before list to avoid cases. Imagine, we have list 1, 2, 3, 4, 5, 6, let us add 0 node in the beginning, so we have 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 now.

Now, let us look at the main step of algorithm (for simplicity I will call nodes by its values)

  1. pre = 0, whe check if pre.next and pre.next.next exists, they are, so define a = 1 and b = 2.
  2. Now, we need to rewrite links: 0 -> 2, 2 -> 1 and 1 -> 3. Note, that we do it all in one step.
  3. Finally, we say, that pre = 1. Also, our list now looks like 0 -> 2 -> 1 -> 3 -> 4 -> 5 -> 6 and as I said pre = 1 now, so we swapped first two elements and now we on element number 2, which is exaclty what we have previously for smaller list.
  4. On next step we have 0 -> 2 -> 1 -> 4 -> 3 -> 5 -> 6 and finally 0 -> 2 -> 1 -> 4 -> 3 -> 6 -> 5, this is exaclty what we need to return.

Complexity

Time complexity is O(n): we iterate over our list once, space complexity is O(1): we did not add any new space and reused already existing nodes.

class Solution:
    def swapPairs(self, head):
        dummy = ListNode(-1)
        dummy.next = head
        pre = dummy
        while pre.next and pre.next.next:
            a = pre.next
            b = a.next
            pre.next, b.next, a.next = b, a, b.next
            pre = a
        return dummy.next