Swap Nodes in Pairs – LeetCode 24 Solution

If you’re a LeetCode enthusiast or just starting out, you might have encountered the problem Swap Nodes in Pairs (LeetCode 24). This is a classic problem that involves swapping adjacent nodes in a linked list. Understanding how to solve this problem is crucial for mastering linked list manipulation and performing well in coding interviews.

In this blog post, we’ll break down the problem, discuss the optimal approach to solve it, and provide the Java solution along with a step-by-step explanation.

Problem Statement: Swap Nodes in Pairs

Given a linked list, the task is to swap every two adjacent nodes. You need to perform the operation in-place, meaning without creating any new nodes or arrays. The function signature looks something like this:

public ListNode swapPairs(ListNode head);

Example 1:

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

Output: [2,1,4,3]

Explanation:

Example 2:

Input: head = []

Output: []

Example 3:

Input: head = [1]

Output: [1]

Example 4:

Input: head = [1,2,3]

Output: [2,1,3]

Constraints:

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

Approach to Solve the Swap Nodes in Pairs

Step 1: Understand the Basic Idea

The problem asks us to swap every two adjacent nodes. For example:

• Given 1 -> 2 -> 3 -> 4, after swapping the adjacent nodes, it should become 2 -> 1 -> 4 -> 3.

Step 2: Handle Edge Cases

Before diving into the solution, let’s consider some edge cases:

• If the linked list is empty, return null.
• If the linked list has only one node, return the list as it is (no swap needed).

Step 3: Iterative Approach

The most efficient way to swap nodes in pairs without extra space is by using an iterative approach. Here’s how:

• Use a dummy node to simplify handling the head of the list.
• Traverse the linked list in pairs of nodes, performing the swap for each pair.
• After swapping each pair, adjust the pointers accordingly.

Step 4: Code Implementation

Now, let’s implement the solution in Java.

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Solution {
    public ListNode swapPairs(ListNode head) {
        // Edge case: if the list is empty or has only one element
        if (head == null || head.next == null) {
            return head;
        }

        // Dummy node to simplify edge cases
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        
        // Traverse the list in pairs
        while (head != null && head.next != null) {
            ListNode first = head;
            ListNode second = head.next;
            
            // Swapping the nodes
            prev.next = second;
            first.next = second.next;
            second.next = first;
            
            // Move the prev and head pointers two nodes ahead
            prev = first;
            head = first.next;
        }
        
        return dummy.next; // Return the new head of the list
    }
}

Explanation of the Code

1. ListNode Class: The ListNode class represents a node in the singly linked list, where val stores the value and next points to the next node.
2. Edge Case Handling: We check if the head is null or if the list has only one node. If either condition is true, we simply return the head.
3. Dummy Node: We create a dummy node to simplify handling the head of the linked list. This allows us to avoid additional checks for the head node during the swaps.
4. While Loop: The loop iterates through the list in pairs. For each pair:
   • first points to the first node of the pair.
   • second points to the second node of the pair.
   • The pointers are updated to swap the nodes.
5. Return: After performing all the swaps, we return the new head of the list (which is dummy.next).

Time Complexity for Swap Nodes in Pairs:

• The time complexity of this solution is O(n), where n is the number of nodes in the linked list. We traverse the list once, swapping adjacent nodes.

Space Complexity for Swap Nodes in Pairs:

• The space complexity is O(1) as we are using a constant amount of extra space (only a few pointers).

Conclusion

The Swap Nodes in Pairs problem is an excellent way to practice working with linked lists and pointers. By understanding the problem and applying an iterative approach, we can solve this efficiently in O(n) time with O(1) space. This solution works well for various test cases and edge conditions.

With this understanding, you can confidently approach this problem in coding interviews or practice platforms like LeetCode.

Feel free to ask questions or leave comments if you need further clarification!