Solving Leetcode 24. Swap Nodes in Pairs

Problem Stated From Leetcode: 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.)

Given a linked list:

Before: `[a, b, c, d]`

After : `[b, a, d, c]`

We can solve this problem iteratively or recursively. The idea is that we need to keep track of the previous node and the current node so that we can link them back together after we swap. Let’s look at the iterative solution first:

We create a dummy node to help us keep track of the head (since the head will change after we swap) and set it equal to the current node. We then set up a while loop that will run as long as our current node exists and is not equal to the dummy node (since we don’t want to swap the very first node.) Within the while loop, we set up a temporary variable that will store the value of our current node’s next node. We then set the current node’s next equal to it’s previous node (which we can get by going two nodes back.) Then, we set the previous node’s next equal to our temporary variable (which contains the original next node.) And finally, we update our previous node and current node pointers for the next iteration.

Following Code in Java:

public ListNode swapPairs(ListNode head) {



    if (head == null || head.next == null) return head;



    ListNode dummy = new ListNode(-999);

    dummy.next = head;



    ListNode prev = dummy;

    ListNode curr = head;



    while (curr != null && curr != dummy) {

        ListNode temp = curr.next;



        curr.next = prev;

        prev.next = temp;



        prev = curr;

        curr = temp;

    }



    // set head and unlink dummy node

    head = dummy.next.next;

    dummy.next.next = null;



    return head;

}

Here is the code also in JavaScript.

/**

 * Definition for singly-linked list.

 * function ListNode(val, next) {

 *     this.val = (val===undefined ? 0 : val)

 *     this.next = (next===undefined ? null : next)

 * }

 */

/**

 * @param {ListNode} head

 * @return {ListNode}

 */

var swapPairs = function(head) {

     if(head === null || head.next === null) {

        return head;

    }

    var dummy = new ListNode(0);

    dummy.next = head;

    var current = dummy;

    while(current.next !== null && current.next.next !== null) {

        var firstNode = current.next;

        var secondNode = current.next.next;

        firstNode.next = secondNode.next;

        current.next = secondNode;

        current.next.next = firstNode;

        current = current.next.next;

    }

    return dummy.next;

};

We can also solve this problem recursively, which may be easier to understand if you are not familiar with linked lists. The idea is that we want to swap the current node with it’s next node, but we need to do this in a way that will work for the rest of the list. So we recursively call the `swapPairs` method on the next node’s next, and then set the current node’s next equal to that. Finally, we set the next node’s next equal to the current node.

Here is the code in Java:

public ListNode swapPairs(ListNode head) {

if (head == null || head.next == null) return head;

// swap with next node

ListNode temp = head.next;

head.next = swapPairs(temp.next);

temp.next = head;

return temp;

}

Both of these solutions run in O(n) time and O(n) space. Hope this helped! Let me know if you have any questions. 🙂