24. Swap Nodes in Pairs

Swap Nodes in Pairs

Problem Description

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

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]

Example 2:

Input: head = []
Output: []

Example 3:

Input: head = [1]
Output: [1]

 

Constraints:

• The number of nodes in the list is in the range [0, 100].
• 0 <= Node.val <= 100

Iterative Approach)

/**
 * 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}
 */

let size = function(node){
    let count = 0;
    while(node){
        node = node.next;
        count++;
    }
    return count;
}

var swapPairs = function(head) {
    
    if(size(head) < 2){
        return head;
    }
    
    const dummy = new ListNode(0);
    dummy.next = head;
    let current = dummy;
    
    while(current.next != null && current.next.next != null){
        let first = current.next;
        let second = current.next.next;
        first.next = second.next;
        current.next = second;
        current.next.next = first;
        current = current.next.next;  
    }
    
    return dummy.next;
    
};

W / Recursion Approach

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    // Return head if no pairs left
    if (head == null || head.next == null) return head;
    
                                                // 1) first -> second -> third
    const next = head.next;                     // 2) second
    head.next = swapPairs(head.next.next);      // 3) first -> third
    next.next = head;                           // 4) second -> first
                                                // 5) second -> first -> third
    
    // Return first node of the swapped pair
    // This will be used as the 'third' node during recursion (step 3)
    return next;                                        
};

Runtime: 65 ms, faster than 91.65% of JavaScript online submissions for Swap Nodes in Pairs.
Memory Usage: 42.1 MB, less than 70.51% of JavaScript online submissions for Swap Nodes in Pairs.

Resources:

https://github.com/PraveenMistry/leetCode

https://medium.com/@praveenmistry/linked-list-javascript-part-3-1-d504f0c9b54e

https://medium.com/@praveenmistry/doubly-linked-list-javascript-part-3-2-1209068fb788

Conclusion

That’s all folks! In this post, we solved LeetCode problem #24. Swap Nodes in Pairs

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to collect & present the most important points to consider when improving Data structure and logic, feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!