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), returnNone. - 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 (
valattributes). This rules out swapping integer data directly, forcing us to rewire thenextreferences.
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
- Initialize a dummy node pointing to the original
head. This acts as a placeholder for the previous pointer (prev). - Set up pointers:
curr = dummyand iterate while there are at least two nodes remaining (i.e.,curr.nextexists ANDcurr.next.nextexists). - Inside the loop, identify the pair:
first_node = curr.nextsecond_node = first_node.next
- Perform the pointer swap logic:
- Make
first_nodepoint to whatever comes aftersecond_node. (curr.next.next) - Make
second_nodepoint back tofirst_node.
- Make
- Advance pointers by two steps so we can process the next pair.
- 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 (
headisNone): The loop condition fails immediately, returnsdummy.nextwhich 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.