LeetCode 24 Swap nodes in pairs

13 Mar 2022

the question describe

The question is 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.)

LeetCode will give you a link, you need swap it exactly, like follow pic

given link list and final link list

Let’s understand the approach

First, we will place a dummy node before a head node so that the code we write can be applicable to the head node also, and we don’t have to specifically write different conditions for the head node.

add dummy node before head node

Now, let the head be our n1 node and next be n2 node, that means node with value 1 is n1 and node with value 2 is n2, and we have to swap n1 and n2. So for this, we will also have to keep track of the node previous to n1 node, let it be prev, as it’s next pointer value will have to change after we swap the n1 node and n2 node
Now the very first thing to do is change the next pointer of prev node to point to n2 node. Why?? Because in the answer we want the n2 node after dummy node. Right? So we will have to connect dummy node(now is prev node) to the node with value 2(n2 node). The means
```
prev.next = n2
```
Now in our final answer the node with value 1 should be at the place of node with value 2. So the next pointer of node with value 1 should point to whatever the node with value 2 is pointing to originally. That means we will have to change n1 next to n2 next
```
n1.next = n2.next
```
Now as in the answer the node with value 2 should point to node with value 1. That means
```
n2.next = n1
```
After this iteration, Nodes 1 and 2 will get swapped and our linked list will look like this
Now for the next iteration, we have to swap node with values 3 and 4. For that the prev node should point to node with value 1 and the head node should point to node with value 3. This means
```
prev = n1
head = n1.next
```
We should stop this procedure when either there is no nodes left to swap or there is only one node left which cannot be swapped with any node.
At the end, as we can see that our head of the list has been misplaced in the procedure of swapping, so we can return dummy.next to return the swapped linked list.

code

var swapPairs = function(head) {
    // build a dummy nodes link to head, like [-1,1,2,3,4]
    let dummy = new ListNode(-1)
    dummy.next = head
    // assign dummy to prev because prev will change to  forward nodes, but dummy always link to first node, in this example is link to [2...]
    let prev = dummy
    
    // loop when head and head.next is not null
    while(head && head.next) {
        // cur node
        let n1 = head
        // next node
        let n2 = head.next
        
        // link to next node, first time is [2...]
        prev.next = n2 
        // swap
        n1.next = n2.next
        n2.next = n1

        // make prev move to forward node for next loop use, for example, first time prev assign to n1, when next loop prev.next like n1.next [1,3,4]
        prev = n1 
        // change head is n1.next
        head = n1.next
    }

    return dummy.next
};

Complexity: TC = O(n) SC = O(1)

Another solution: recursion

First, we set some rules to stop recursion, if no current node or next node, stop recursion
```
if(!head || !head.next) return head
```
Now we make three variables that v1 represent current node and v2 is next node and v3 is node next the v2 for recursion
```
let v1 = head
let v2 = v1.next
let v3 = v2.next
```
Now we change v2 link to v1. And we assign recursion v3 to v1. That means
```
v1.next = recursionFn(v3)
```
Why do we always return v2? Because after swap nodes, v2 represent the first node in the list, the first time is node with value 2, the second time is node with value 4

code

var swapPairs = function(head) {
    // recursion terminator
    if(!head || !head.next) return head
    // process logic in current level
    let v1 = head
    let v2 = v1.next
    let v3 = v2.next
    v2.next = v1
    // drill down
    v1.next = swapPairs(v3)
    return  v2
}

Complexity TC = O(N) SC = O(1)

reference

24. Swap Nodes in Pairs