How do you solve Swap Nodes in Pairs?

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.

Swap Nodes in Pairs

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.

Q: 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.

Medium In-place Reversal of a Linked List

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

Preview

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…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use a dummy node pointing to the head to handle head swaps uniformly. Maintain a 'prev' pointer to the node before the current pair…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

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.

Pattern Spotlight

Linked List (Pointer Manipulation for Node Swapping)

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.

Solution

Python

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

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.

Iteratively Swap Adjacent Node Pairs by Re-linking Pointers

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

Return the New Head of the Swapped List

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

2 more steps with full analysis available on Pro.

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.

Full line-by-line criticality + rationale for all 12 lines available on Pro.

Test Your Understanding

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

See the answer with Pro.

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`