LeetCode 24: Swap Nodes in Pairs Solution in Python Explained

Problem Statement

LeetCode 24, Swap Nodes in Pairs, is a medium-level challenge where you’re given the head of a linked list and need to swap every two adjacent nodes, returning the head of the modified list. You must swap the nodes themselves (not their values), and the list can have an even or odd number of nodes, with any remaining single node staying as-is.

Constraints

  • Number of nodes in the list is between 0 and 100.
  • 0 <= Node.val <= 100: Node values range from 0 to 100.

Example

Input: head = [1,2,3,4]
Output: [2,1,4,3]
Explanation: Swap 1-2 and 3-4.

Input: head = []
Output: []
Explanation: Empty list remains empty.

Input: head = [1]
Output: [1]
Explanation: Single node stays unchanged.

Understanding the Problem

How do you solve LeetCode 24: Swap Nodes in Pairs in Python? Imagine a linked list like [1,2,3,4]. You need to transform it into [2,1,4,3] by swapping each pair—1 with 2, and 3 with 4. Since it’s a linked list, we manipulate pointers to swap nodes, not just their values. For an odd-length list like [1,2,3], swap 1 and 2, leaving 3 alone: [2,1,3]. We’ll explore two solutions: an Iterative Approach (using pointers) and a Recursive Approach (using function calls).

Solution 1: Iterative Approach (Primary)

Explanation

Use a dummy node and a pointer to traverse the list, swapping pairs iteratively by adjusting links. For each pair, rewire the pointers to reverse their order, then move to the next pair.

Here’s a visual for [1,2,3,4]:

Before: dummy -> 1 -> 2 -> 3 -> 4
Swap 1-2: dummy -> 2 -> 1 -> 3 -> 4
Swap 3-4: dummy -> 2 -> 1 -> 4 -> 3
  1. Handle Edge Case.
  • If list is empty or has one node, return as-is.
  1. Create Dummy Node.
  • Use a dummy to simplify pointer adjustments.
  1. Swap Pairs.
  • For each pair, adjust links to swap nodes, move pointer forward.
  1. Return Head.
  • Return dummy.next as the new head.

Step-by-Step Example

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

We have [1,2,3,4] and want [2,1,4,3].

  • Goal: Swap pairs to get [2,1,4,3].
  • Result for Reference: [2,1,4,3].
  • Start: Dummy node, prev points to dummy, list: dummy -> 1 -> 2 -> 3 -> 4.
  • Step 1: Check edge case.
    • Length > 1, proceed.
  • Step 2: Swap first pair (1,2).
    • prev = dummy, curr = 1, next_node = 2.
    • Save next_next = 3.
    • curr.next = next_next (1 -> 3).
    • next_node.next = curr (2 -> 1).
    • prev.next = next_node (dummy -> 2).
    • List: dummy -> 2 -> 1 -> 3 -> 4.
    • Move prev to curr (1), curr to next_next (3).
  • Step 3: Swap second pair (3,4).
    • prev = 1, curr = 3, next_node = 4.
    • next_next = null.
    • curr.next = null (3 -> null).
    • next_node.next = curr (4 -> 3).
    • prev.next = next_node (1 -> 4).
    • List: dummy -> 2 -> 1 -> 4 -> 3.
  • Step 4: No more pairs, stop.
  • Finish: Return dummy.next: [2,1,4,3].

Example 2: head = [1]

Now, [1] with one node.

  • Goal: Swap pairs (none to swap).
  • Result for Reference: [1].
  • Start: Dummy -> 1.
  • Step 1: Check edge case.
    • Head.next is null, return head.
  • Finish: Return [1].

How the Code Works (Iterative)

Here’s the Python code with line-by-line explanation:

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

def swapPairs(head: ListNode) -> ListNode:
    # Line 1: Check if list is empty or single node
    if not head or not head.next:
        # Line 2: Return head as-is if no pairs to swap
        return head

    # Line 3: Create dummy node to simplify linking
    dummy = ListNode(0)
    # Line 4: Link dummy to head
    dummy.next = head
    # Line 5: Set prev pointer to dummy for first pair
    prev = dummy

    # Line 6: Loop while at least two nodes remain
    while prev.next and prev.next.next:
        # Line 7: Current node (first of pair)
        curr = prev.next
        # Line 8: Next node (second of pair)
        next_node = curr.next
        # Line 9: Save pointer to next pair or null
        next_next = next_node.next

        # Line 10: Link current to next pair (skip next_node)
        curr.next = next_next
        # Line 11: Link next_node to current (swap)
        next_node.next = curr
        # Line 12: Link prev to next_node (new first)
        prev.next = next_node

        # Line 13: Move prev two steps to next pair
        prev = curr

    # Line 14: Return head of swapped list
    return dummy.next

Alternative: Recursive Approach

Explanation

Recursively swap pairs by handling the first two nodes and linking to the result of swapping the rest. Base cases stop recursion when fewer than two nodes remain.

  1. Base Cases.
  • Empty or single node returns as-is.
  1. Swap First Pair.
  • Take first two nodes, reverse their links.
  1. Recurse.
  • Link second node’s next to result of swapping remaining list.
  1. Return New Head.
  • Return swapped pair’s head.

Step-by-Step Example (Recursive)

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

  • Goal: Swap to [2,1,4,3].
  • Result for Reference: [2,1,4,3].
  • Step 1: swapPairs(1->2->3->4).
    • Not null or single, swap 1,2.
    • next_node = 2, next_next = 3.
    • 2.next = swapPairs(3->4).
  • Step 2: swapPairs(3->4).
    • Swap 3,4.
    • next_node = 4, next_next = null.
    • 4.next = swapPairs(null) = null.
    • 3.next = null, return 4->3.
  • Step 3: Back to step 1.
    • 2.next = 4->3.
    • 1.next = null (temp), link to 2 later.
    • Return 2->1->4->3.
  • Finish: [2,1,4,3].

How the Code Works (Recursive)

Here’s the recursive Python code with explanations:

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

def swapPairsRecursive(head: ListNode) -> ListNode:
    # Line 1: Base case - empty or single node
    if not head or not head.next:
        # Line 2: Return head as-is
        return head

    # Line 3: First node of pair
    curr = head
    # Line 4: Second node of pair
    next_node = curr.next
    # Line 5: Save rest of list
    next_next = next_node.next

    # Line 6: Swap by linking second to first
    next_node.next = curr
    # Line 7: Recursively swap rest, link to first
    curr.next = swapPairsRecursive(next_next)

    # Line 8: Return new head (second node)
    return next_node

Complexity

  • Iterative:
    • Time: O(n) – Single pass, n is list length.
    • Space: O(1) – Only pointers.
  • Recursive:
    • Time: O(n) – Recursion depth n/2, O(n) total.
    • Space: O(n) – Recursion stack.

Efficiency Notes

Both solutions run in O(n) time, but iterative uses O(1) space, making it more efficient for memory. Recursive is elegant but consumes stack space, less ideal for very long lists.

Key Insights

Tips to master LeetCode 24:

  • Dummy Saves Edge Cases: Iterative approach simplifies head swaps.
  • Pointers Rule: Both methods rely on precise pointer manipulation.
  • Pairs Focus: Handle two nodes at a time—keep it simple!

Additional Example

For head = [1,2,3]:

  • Goal: Swap to [2,1,3].
  • Iterative: Dummy -> 2 -> 1 -> 3.
  • Recursive: 2 -> 1 -> swap(3) -> 3.
  • Result: [2,1,3].

Edge Cases

  • Empty: [] – Returns null.
  • Single: [1] – Returns [1].
  • Odd Length: [1,2,3] – Returns [2,1,3].

Final Thoughts

The iterative approach is efficient and practical for LeetCode 24 in Python, while recursive offers elegance. Check LeetCode 19: Remove Nth Node for more linked list practice!