LeetCode 24 Solution: Swap Nodes in Pairs Explained

The LeetCode 24 solution to the swap nodes in pairs problem involves swapping every two adjacent nodes in a linked list without changing their values. This classic problem tests your ability to manipulate linked lists efficiently by adjusting pointers, making it a great exercise for interview preparation. Let’s dive into the problem, explore a Python solution, and understand how to handle various edge cases along the way.

Understanding the Problem

The task in the LeetCode 24 problem is straightforward: given a linked list, we need to swap every two adjacent nodes and return the head of the modified list. The key requirement here is that we cannot change the values of the nodes—we must swap the nodes themselves.

For example, consider the linked list 1 -> 2 -> 3 -> 4. After swapping every two nodes, the list should look like 2 -> 1 -> 4 -> 3. Notice that the positions of the nodes change, but their values remain the same.

An important detail to remember is that if the list has an odd number of nodes, the last node remains in its original position, as it does not have a pair to swap with. For instance, in the list 1 -> 2 -> 3, the result after swapping would be 2 -> 1 -> 3.

Approach to Solve Swap Nodes in Pairs

To solve this problem, we need to traverse the linked list two nodes at a time. For each pair of adjacent nodes, we swap their positions by adjusting their pointers. We’ll use a temporary dummy node to simplify handling the head of the list, especially when the head itself is part of the pair to be swapped.

Here’s the general idea:

1. Use a dummy node that points to the head of the list. This dummy node helps us easily manage edge cases.
2. Traverse the list while there are at least two nodes to swap. For each pair, change their pointers to swap them.
3. Once all pairs are swapped, return the new head of the modified list.

By maintaining a few pointers and carefully reassigning them during each swap, we can achieve the desired result without modifying the node values, which satisfies the problem’s constraints.

LeetCode 24 Python Code Solution

Here’s a clean and readable Python implementation for the LeetCode 24 problem:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def swapPairs(head: ListNode) -> ListNode:
    # A dummy node simplifies edge cases and head swapping
    dummy = ListNode(0)
    dummy.next = head
    prev = dummy

    # Traverse the list while there are pairs to swap
    while head and head.next:
        first = head          # First node in the pair
        second = head.next    # Second node in the pair

        # Perform the swap by adjusting pointers
        prev.next = second    # Link previous node to the second node
        first.next = second.next  # Link first node to the node after the pair
        second.next = first   # Complete the swap by linking second to first

        # Move to the next pair
        prev = first          # Update prev to the last node in the swapped pair
        head = first.next     # Move head to the next pair of nodes

    # The dummy node's next points to the new head
    return dummy.next

Analyzing the Solution

The solution uses three main pointers:

• prev: Keeps track of the node before the pair being swapped.
• first: Refers to the first node in the current pair.
• second: Refers to the second node in the pair.

By manipulating these pointers in each iteration of the loop, we successfully swap the nodes without needing extra memory or complex operations.

Edge Cases to Consider

In any linked list problem, it’s crucial to think about edge cases. This solution gracefully handles several possible edge cases:

• Empty List: If the list is empty (head = None), the function returns None, as there are no nodes to swap.
• Single Node List: In a list with just one node ([1]), there’s no adjacent node to swap, so the list remains unchanged.
• Even Length List: In a list like [1, 2, 3, 4], the function correctly swaps pairs, producing 2 -> 1 -> 4 -> 3.
• Odd Length List: If the list has an odd number of nodes, such as [1, 2, 3], only the first two nodes are swapped, and the last node remains as it is.

Time and Space Complexity

The time complexity of the solution is O(n), where n is the number of nodes in the linked list. This is because we traverse the entire list, visiting each node exactly once.

The space complexity is O(1), as the solution only uses a few extra pointers (prev, first, second) and does not require additional memory proportional to the size of the list.

Conclusion

The LeetCode 24 Solution for the swap nodes in pairs problem is an excellent exercise in linked list manipulation. It teaches you how to handle linked list pointers efficiently and swap nodes in constant time without extra memory usage. By carefully planning the pointer reassignments, we can ensure that the solution works efficiently even for larger lists with up to 100 nodes.

For anyone preparing for coding interviews or practicing linked list problems, this problem is an essential one to master. The Python solution provided here not only solves the problem within optimal time and space limits, but it also demonstrates how to handle edge cases and maintain clean, readable code.

If you’re new to linked lists or looking to deepen your understanding, make sure to practice this problem and similar ones to build your confidence in handling node manipulation!

Happy Coding!

---

Looking for more LeetCode solutions? Stay tuned for upcoming guides on tackling other LeetCode challenges in Python. Whether you’re preparing for technical interviews or aiming to improve your coding skills, exploring a variety of problems will enhance your understanding and proficiency.

You can find this problem on LeedCode, click here.