A LeetCode Daily Series — Day 89

Today’s problem is called "Swap Nodes in Pairs"

Updated: at 02:24 AM

In this article, we’ll explore how to swap every two adjacent nodes in a singly linked list, a common problem that can test our understanding of linked list manipulation and pointer handling. Let’s get started!

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

Cover Image

Understanding the Problem

Given a linked list, the task is to swap every two adjacent nodes and return the head of the modified list. The important constraint here is that we are not allowed to modify the values of the nodes themselves but only the nodes. This means that our solution must involve changing the pointers of the nodes rather than their values.

Let’s look at some examples:

Example 1: 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]

Using Efficient Approach: Pointer Manipulation

To solve this problem efficiently, we will use a pointer manipulation approach. The idea is to use a dummy node to simplify edge cases and then iterate through the list, swapping nodes in pairs.

def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head

    dummy = ListNode()
    curr = head
    prev = dummy

    while curr and curr.next:
        prev.next = curr.next
        curr.next = prev.next.next
        prev.next.next = curr

        prev = curr
        curr = curr.next

    return dummy.next

Explanation

  1. Initial Checks: The function starts by checking if the list is empty or has only one node. If so, it returns the head as no swapping is needed.
  2. Dummy Node: A dummy node is created to handle edge cases easily. This node does not hold any value but points to the head of the list.
  3. Pointers Initialization: Three pointers are initialized:
    • curr points to the current node being processed (initially the head of the list).
    • prev points to the node before the current pair (initially the dummy node).
  4. Swapping Nodes: The loop runs as long as there are pairs to swap:
    • prev.next is set to point to the second node of the current pair.
    • curr.next is adjusted to point to the node after the pair.
    • The second node’s next is adjusted to point to the first node.
    • prev and curr pointers are then moved forward to the next pair of nodes.
  5. Return New Head: Finally, the new head of the modified list is returned, which is dummy.next.

Variable States for Each Iteration

Let’s walk through an example with the list [1, 2, 3, 4]:

  1. Initial State:
dummy -> [0] -> [1] -> [2] -> [3] -> [4]
curr -> [1]
prev -> [0]
  1. First Iteration:
# Swapping nodes [1] and [2]
prev.next -> [2]
curr.next -> [3]
prev.next.next -> [1]
# Update pointers:
prev -> [1]
curr -> [3]
  1. Second Iteration:
# Swapping nodes [3] and [4]
prev.next -> [4]
curr.next -> None
prev.next.next -> [3]
# Update pointers:
prev -> [3]
curr -> None

Time Complexity: O(n) - We traverse the list once, making the operation linear in relation to the number of nodes.

Space Complexity: O(1) - We only use a few extra pointers, making the space overhead constant.

Results

Conclusion

In this article, we tackled the problem of swapping every two adjacent nodes in a linked list by using an efficient pointer manipulation approach. We explored the problem, broke down the solution, and understood the code step-by-step.

By mastering this approach, you’re well-equipped to handle more complex linked list manipulation problems.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series