LeetCode #24: Swap Nodes in Pairs

Hello, coding enthusiasts! Today, we’re solving the “Swap Nodes in Pairs” problem from LeetCode using Python and JavaScript.

Problem Statement

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

Analysis

This problem is a classic example of a linked list manipulation problem. The main challenge here is to correctly swap the nodes and adjust the pointers without losing any nodes.

The problem can be solved using a recursive approach. The idea is to swap the first two nodes and then recursively swap the remaining nodes.

Approach

Here’s a step-by-step approach to solve this problem:

Base Case: If the list is empty or has only one node, we return the list as it is.
Swap Nodes: We swap the first two nodes of the list.
Recursive Call: We make a recursive call to the rest of the list and attach it to the second node (which is now the first node after the swap).
Return New Head: Finally, we return the new head of the list.

Time Complexity

The time complexity of this approach is O(n), where n is the number of nodes in the list. This is because we are processing each node exactly once.

Space Complexity

The space complexity is O(n), due to the recursive stack. In the worst case, the depth of the recursive call stack will be n/2, which is O(n).

Code

Python

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        # Base case
        if not head or not head.next:
            return head
        
        # Nodes to be swapped
        first_node = head
        second_node = head.next
        
        # Swapping
        first_node.next = self.swapPairs(second_node.next)
        second_node.next = first_node
        
        # Now the head is the second node
        return second_node

JavaScript

var swapPairs = function(head) {
    // Base case
    if (!head || !head.next) {
        return head;
    }
    // Nodes to be swapped
    let firstNode = head;
    let secondNode = head.next;
    
    // Swapping
    firstNode.next = swapPairs(secondNode.next);
    secondNode.next = firstNode;
    
    // Now the head is the secondNode
    return secondNode;
};

Conclusion

In this post, we tackled the “Swap Nodes in Pairs” problem from LeetCode. We used a recursive approach to swap the nodes in pairs.

The time complexity of this approach is O(n), and the space complexity is also O(n) due to the recursive stack.

Happy coding!

Learn More: