Swap Nodes In Pairs Leetcode Problem 24 [Python Solution]

In this blog post, we face the Swap Nodes In Pairs problem, which is LeetCode Problem 24. The goal is to take a linked list and swap every two adjacent nodes, returning the modified list’s head.

It’s important to note that we can’t modify the values within the nodes; we can only change the connections between nodes.

Let’s break this problem down step by step, providing a Python solution and explanations for each part.

Understanding the Problem

Example 1:

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

Constraints

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

Before we dive into the code, let’s understand the key components of this problem.

Efficient Python Code Solution

def swapPairs(self, head: ListNode) -> ListNode:
    # Create a dummy node
    dummy = ListNode(0, head)
    prev, curr = dummy, head

    while curr and curr.next:
        # Save pointers to the next pair and the second node
        nxtPair = curr.next.next
        second = curr.next

        # Reverse this pair
        second.next = curr
        curr.next = nxtPair
        prev.next = second

        # Update pointers for the next iteration
        prev = curr
        curr = nxtPair

    return dummy.next

Reasoning Behind Our Approach

The key to solving this problem efficiently is to use a dummy node to simplify the edge cases and avoid complications.

We follow these steps in the solution:

1. Create a dummy node with a value of 0 and set its next pointer to the original head of the list.

2. Initialize two pointers, prev and curr. prev points to the dummy node, and curr starts at the head of the list.

3. We iterate through the list as long as there are at least two nodes to swap (i.e., curr and curr.next are not None).

4. Inside the loop, we save pointers to the next pair and the second node.

These are crucial for our swaps.

1. We reverse the pair by updating the next pointers.

The second node’s next now points to the first node, and the first node’s next points to what was initially the next pair.

1. We update the prev pointer to the second node.

This keeps track of the connection between the previous pair and the current pair, making it easy to link them correctly.

1. We update the curr pointer to the nxtPair to prepare for the next iteration.

2. Finally, we return dummy.next, which points to the new head of the modified list.

This approach is efficient with a time complexity of O(n) since we only loop through the list once.

The space complexity is O(1) because we don’t use any additional data structures.

Related Interview Questions By Company:

• Insert Interval LeetCode
• Walls And Gates LeetCode
• Count Good Nodes In Binary Tree LeetCode

Related Interview Questions By Difficulty:

• Reverse Linked List LeetCode
• Swap Nodes In Pairs LeetCode
• Design Circular Queue LeetCode

Related Interview Questions By Category:

• Valid Perfect Square LeetCode
• Last Stone Weight II LeetCode
• Triangle LeetCode

Conclusion

In this blog post, we’ve explored the Swap Nodes In Pairs problem on LeetCode, providing a Python solution and a detailed explanation of our approach.

By using a dummy node and carefully managing our pointers, we can efficiently swap adjacent nodes in a linked list.

If you found this guide helpful, please like and engage to support the our platform.

Feel free to comment, ask questions, make suggestions, and share this content with others who might find it useful.

For more details and the original question, you can visit the Swap Nodes in Pairs LeetCode problem.

Happy coding!