Domain 2MediumCORE

Swap Nodes in Pairs

We are given the head of a singly linked list and need to return its new head after swapping every two adjacent nodes in pairs. For example, [1, 2, 3, 4] becomes [2, 1, 4, 3].

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Linked List#Recursion

24. Swap Nodes in Pairs

Model: qwen3.5:9b
Topics: Linked List,Recursion
FAANG asked: 1
Acceptance rate: 53.5%


Problem Breakdown

We are given the head of a singly linked list and need to return its new head after swapping every two adjacent nodes in pairs. For example, [1, 2, 3, 4] becomes [2, 1, 4, 3].

Key inputs: A ListNode object representing the start of the chain. Output: The modified linked list’s new head node.

Implicit constraints and edge cases to consider immediately:

  • Empty List: If input is empty (None), return None.
  • Single Node: Swapping requires a pair; if only one node exists, it remains unchanged at the end of the chain.
  • Odd Length Lists: The last node will not have a partner to swap with and stays in place after its predecessor is swapped into position.
  • Follow-up Constraint: We must manipulate pointers (nodes), not values (val attributes). This rules out swapping integer data directly, forcing us to rewire the next references.

Intuition

The naive approach might be to swap the .val of adjacent nodes and move forward by two steps. However, this violates the follow-up constraint regarding pointer manipulation.

To solve this without modifying values, we need to change where each node points (next). If I visualize a pair like A -> B, after swapping it becomes B -> A. The tricky part is linking these pairs together correctly and handling the new head of the list (which will be the second element of the first pair).

I can solve this iteratively or recursively. Iterative is generally preferred in production environments to avoid stack overflow risks, though with N=100 it doesn’t matter much here. I’ll use an iterative approach because it demonstrates explicit control over memory and pointer logic without relying on call stacks.

The core insight for linked list manipulation problems involving pairs is using a dummy node. Why? Because the first swap changes which node becomes the head of the entire list (the second element of the pair). A dummy node simplifies returning head to just dummy.next, avoiding special logic inside the loop to handle the very first iteration.

Approach

  1. Initialize a dummy node pointing to the original head. This acts as a placeholder for the previous pointer (prev).
  2. Set up pointers: curr = dummy and iterate while there are at least two nodes remaining (i.e., curr.next exists AND curr.next.next exists).
  3. Inside the loop, identify the pair:
    • first_node = curr.next
    • second_node = first_node.next
  4. Perform the pointer swap logic:
    • Make first_node point to whatever comes after second_node. (curr.next.next)
    • Make second_node point back to first_node.
  5. Advance pointers by two steps so we can process the next pair.
  6. Return dummy.next, which is now guaranteed to be the new head of the list.

Complexity Analysis

  • Time Complexity: O(N), where N is the number of nodes in the linked list. We traverse each node exactly once (or rather, we visit every node as part of a pair check).
  • Space Complexity: O(1) for an iterative solution. We only use a constant amount of extra pointers (dummy, curr, etc.) regardless of input size. If implemented recursively, it would be O(N/2) stack space due to the call depth.

Solution

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

def swapPairs(head: 'ListNode') -> 'ListNode':
    # Create a dummy node to simplify edge cases where the head changes.
    # This ensures we always have a valid previous pointer (prev).
    dummy = ListNode(0)
    prev = dummy
    
    current_node = head
    
    # Continue as long as there are at least two nodes left in the list
    while current_node and current_node.next:
        first_node = current_node       # The node that will move to second position (new pair start)
        second_node = current_node.next # The node that becomes new head of this pair
        
        # Perform pointer manipulation without changing values
        # 1. Link the rest of the list after 'second_node' back to 'first_node'
        first_node.next = second_node.next 
        
        # 2. Swap pointers: make 'second_node' point to 'first_node'
        second_node.next = first_node
        
        # 3. Move prev forward by two steps (skipping the swapped pair)
        prev.next = second_node 
        current_node = first_node.next
    
    return dummy.next

Edge Cases Handled

  • Empty List (head is None): The loop condition fails immediately, returns dummy.next which remains pointing to original head (which was None), correctly returning an empty list.
  • Single Node: Loop checks current_node and current_node.next. If only one node exists, the second part of AND evaluates false. Loop terminates, single node is returned unchanged as expected.
  • Odd Number of Nodes: The loop processes pairs until fewer than two nodes remain. The last unpaired node remains attached to its predecessor via standard pointer logic without entering a swap block.