What pattern does Swap Nodes in Pairs use?

The Pattern: Linked List (Pointer Manipulation for Node Swapping) The Heuristic: When swapping nodes in a linked list, use a dummy node and a 'prev' pointer to maintain stable connections before and after the swapped pair, ensuring no nodes are lost and edge cases are handled uniformly.

Swap Nodes in Pairs - LeetCode Solution

Q: What is the time complexity of Swap Nodes in Pairs?

O(n). The algorithm traverses the linked list once, swapping pairs in a single pass, resulting in linear time proportional to the number of nodes.

Problem

Given the head of a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed).

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

Example

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

Output: [2,1,4,3]

Starting with the list 1 -> 2 -> 3 -> 4, the algorithm swaps the first pair (1 and 2) to get 2 -> 1 -> 3 -> 4. Then it swaps the next pair (3 and 4) to get 2 -> 1 -> 4 -> 3. The process continues until all adjacent pairs are swapped or no pair remains.

Approach

Straightforward Solution

A naive approach might try to swap node values instead of nodes, which is disallowed. Another approach is to create a new list and copy nodes in swapped order, which uses extra space and is inefficient.

Core Observation

Swapping nodes in pairs requires careful pointer manipulation to avoid losing access to the rest of the list. Each swap involves re-linking two nodes and connecting the previous part of the list to the new head of the swapped pair.

Path to Optimal

The key insight is to use a dummy node to simplify edge cases and maintain a pointer to the node before the pair being swapped. By iterating through the list in pairs, the algorithm swaps the nodes by adjusting their next pointers, then moves the pointers forward to the next pair.

Optimal Approach

Use a dummy node pointing to the head to handle head swaps uniformly. Maintain a 'prev' pointer to the node before the current pair. For each pair, re-link pointers to swap the two nodes, then advance 'prev' and 'head' pointers to the next pair. Continue until no more pairs remain. Return dummy.next as the new head.

Time

O(n)

The algorithm traverses the linked list once, swapping pairs in a single pass, resulting in linear time proportional to the number of nodes.

Space

O(1)

Only a fixed number of pointers are used for traversal and swapping; no additional data structures proportional to input size are allocated.

Solution

1class Solution:
  def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
      dummy = ListNode(0)
      dummy.next = head
      prev = dummy
6
      while head and head.next:
          first = head
          second = head.next
10
          prev.next = second
          first.next = second.next
          second.next = first
14
          prev = first
          head = first.next
17
      return dummy.next

Step-by-Step Solution

1

Set Up Dummy Node and Initialize Pointers for Pairwise Swapping

3dummy = ListNode(0)
4dummy.next = head
5prev = dummy

Objective

To create a stable starting point and pointers that facilitate swapping pairs without losing track of the list.

Key Insight

Using a dummy node that precedes the head allows uniform handling of swaps, including the first pair. The 'prev' pointer tracks the node before the current pair, enabling reconnection after swapping. Initializing 'head' to the original list head prepares for iteration.

Interview Quick-Check

Core Logic

The dummy node acts as a fixed anchor before the list, preventing edge case complexity when swapping the first pair.

State & Boundaries

Initialize 'prev' to dummy and 'head' to the original head to start swapping from the beginning.

Common Pitfalls & Bugs

Forgetting to set dummy.next = head can cause the returned list to be disconnected or empty.

2

Iteratively Swap Adjacent Node Pairs by Re-linking Pointers

7while head and head.next:
  first = head
  second = head.next
  prev.next = second
  first.next = second.next
  second.next = first
  prev = first
  head = first.next

Objective

To traverse the list in pairs, swapping each pair by adjusting next pointers while maintaining list integrity.

Key Insight

Swapping two nodes involves three pointer updates: connecting 'prev.next' to the second node, linking the first node to the node after the second, and linking the second node to the first. After swapping, 'prev' moves to the first node (now second in the pair), and 'head' advances to the next pair's first node. This process repeats until fewer than two nodes remain.

Interview Quick-Check

Core Logic

Each swap reassigns pointers to reverse the pair order without losing access to the rest of the list.

State & Boundaries

The loop condition 'while head and head.next' ensures pairs exist to swap.

Common Pitfalls & Bugs

Incorrect pointer updates can cause cycles or lost nodes; the order of pointer assignments is critical.

Complexity

The loop advances by two nodes per iteration, ensuring O(n) time complexity.

3

Return the New Head of the Swapped List

18	`return dummy.next`

Objective

To provide the caller with the head of the modified list after all pairs have been swapped.

Key Insight

Since the original head may have changed due to swapping the first pair, returning dummy.next ensures the correct new head is returned regardless of whether the list was empty or had one or more pairs swapped.

Interview Quick-Check

Core Logic

Returning dummy.next returns the head of the fully swapped list, handling all edge cases.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 11 Critical

prev.next = second

Link 'prev.next' to 'second', making the second node the new head of the swapped pair.

This reassignment is the critical step that repositions the second node before the first, enabling the swap without losing access to the list.

Line 13 Critical

second.next = first

Link 'second.next' to 'first', completing the swap by placing 'first' after 'second'.

This line completes the swap by linking the second node to the first, reversing their order in the list.

Line 3 Core

dummy = ListNode(0)

Create a dummy node with value 0 to act as a stable predecessor to the head.

The dummy node simplifies pointer manipulation by providing a fixed node before the head, eliminating special cases when swapping the first pair.

Line 7 Core

while head and head.next:

Start a loop that continues as long as there are at least two nodes to swap.

The condition 'head and head.next' ensures that the current pair exists and can be swapped, preventing null pointer errors.

Line 12 Core

first.next = second.next

Link 'first.next' to the node after 'second', detaching 'first' from 'second'.

This update ensures 'first' points to the remainder of the list beyond the swapped pair, preserving the list structure.

Line 18 Core

return dummy.next

Return the new head of the swapped list, which is dummy.next.

Returning dummy.next accounts for the possibility that the original head was swapped, ensuring the correct list head is returned.

Line 4 Core

dummy.next = head

Link the dummy node's next pointer to the original head of the list.

Connecting dummy.next to head ensures the dummy node anchors the entire list, allowing uniform pointer updates during swaps.

Line 5 Core

prev = dummy

Initialize 'prev' pointer to the dummy node to track the node before the current pair.

The 'prev' pointer is essential for reconnecting the swapped pairs back into the list, maintaining continuity.

Line 15 Core

prev = first

Move 'prev' pointer to 'first', now the second node in the swapped pair.

Advancing 'prev' prepares it to connect to the next pair in subsequent iterations, maintaining the chain.

Line 16 Core

head = first.next

Advance 'head' pointer to the node after 'first', the start of the next pair to swap.

Moving 'head' forward ensures the loop progresses through the list, processing pairs sequentially.

Line 8 Standard

first = head

Assign 'first' to the current head node, representing the first node in the pair.

Naming the first node clarifies the swapping logic and preserves the original node reference for pointer updates.

Line 9 Standard

second = head.next

Assign 'second' to the node following 'first', representing the second node in the pair.

Identifying the second node in the pair is necessary to perform the swap by re-linking pointers.

Test Your Understanding

Why is a dummy node used in the swapping process instead of directly manipulating the head pointer?

The dummy node simplifies edge cases, especially when the head itself is part of the first pair to swap, by providing a stable node before the head, allowing uniform pointer updates without special casing.

Don't just read it. Drill it.

Reconstruct Swap Nodes in Pairs from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Swap Nodes in Pairs drill

or drill a free problem

1	`class Solution:`
2	`def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:`
3	`dummy = ListNode(0)`
4	`dummy.next = head`
5	`prev = dummy`
6
7	`while head and head.next:`
8	`first = head`
9	`second = head.next`
10
11	`prev.next = second`
12	`first.next = second.next`
13	`second.next = first`
14
15	`prev = first`
16	`head = first.next`
17
18	`return dummy.next`

7	`while head and head.next:`
8	`first = head`
9	`second = head.next`
11	`prev.next = second`
12	`first.next = second.next`
13	`second.next = first`
15	`prev = first`
16	`head = first.next`

Problem

Example

Approach

Solution

Step-by-Step Solution

Set Up Dummy Node and Initialize Pointers for Pairwise Swapping

Iteratively Swap Adjacent Node Pairs by Re-linking Pointers

Return the New Head of the Swapped List

Line Analysis

Test Your Understanding

Related Problems

Don't just read it. Drill it.