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. 🙂

Related

How to 10x Your LLM Prompting With DSPy

Tired of spending countless hours tweaking prompts for large...

Google Announces A Cost Effective Gemini Flash

At Google's I/O event, the company unveiled Gemini Flash,...

WordPress vs Strapi: Choosing the Right CMS for Your Needs

With the growing popularity of headless CMS solutions, developers...

JPA vs. JDBC: Comparing the two DB APIs

Introduction The eternal battle rages on between two warring database...

Meta Introduces V-JEPA

The V-JEPA model, proposed by Yann LeCun, is a...

Subscribe to our AI newsletter. Get the latest on news, models, open source and trends.
Don't worry, we won't spam. 😎

You have successfully subscribed to the newsletter

There was an error while trying to send your request. Please try again.

Lusera will use the information you provide on this form to be in touch with you and to provide updates and marketing.