24.swap-nodes-in-pairs.md

24. Swap Nodes in Pairs

Recursive

We define a recursive function to swap the pair.

     current -> next -> nextNext
swap(current -> next) -> f(nextNext)

1 -> 2 -> 3 -> 4

f(1)
= 2 -> 1 -> f(3)

f(3)
= 4 -> 3 -> f(null)

f(null)
= null

fun swapPairs(head: ListNode?): ListNode? {
    if (head == null || head.next == null) return head
    
    // 1 -> 2 -> 3
    // c    n    nn
    val current = head!!
    val next = head.next!!
    val nextNext = next.next

    // 2 -> 1 -> f(nn)
    // n    c
    current.next = swapPairs(nextNext)
    next.next = current
    return next
}

Iterative

We traverse the list by pairs and swap the pair. There are some key points to note:

• We need a sentinel node to simplify the code, and point to the next node after swapping.

1 -> 2 -> 3 -> 4 -> 5
     *
  sentinel

• We need to cache the next next node before we reverse the current pair.

1 -> 2 -> 3 -> 4 -> 5
         (c    n)  nn
                    ^

• We need to relink the previous node after reversing the current pair.

... -> 1 -> (3 -> 4) -> 5
       p     c    n   nn
        \________/

fun swapPairs(head: ListNode?): ListNode? {
    if (head == null || head.next) return null

    // Now we have at least two nodes
    val sentinel = ListNode(-1)
    sentinel.next = head.next // 2, not 1

    var previous: ListNode = sentinel   // or null
    var current: ListNode? = head       // 1
    var next: ListNode? = head.next     // 2
    while (current != null && next != null) {
        // Cache the next next node before we reverse the current pair
        val nextNext = next.next

        // Reverse the current pair: 4 -> 3
        // 2 -> 1 -> 3 -> 4 -> 5
        //           c    n   nn
        //  ...   -> 3 <- 4
        next.next = current

        // Relink the current node: 3 -> 5
        // 2 -> 1 -> 3 -> 4 -> 5
        //           c    n   nn
        //  ...   -> 3 <- 4    5
        //           \________/
        current.next = nextNext

        // Link to previous pair after reversing: 1 -> 4
        // 2 -> 1 -> 3 -> 4
        //      p    c    n
        // 2 -> 1 -> 4 -> 3
        //      p -> n -> c
        //      ^^^^^^
        previous.next = next

        // Move the pointers to next round
        previous = current
        current = nextNext
        next = nextNext?.next
    }

    return sentinel.next
}