Swap Nodes in Pairs

Explanation & Solution

Description

Given 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).

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

Output:[2,1,4,3]

Explanation: Swap nodes 1 and 2, then swap nodes 3 and 4.

Constraints

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

Approach

Fast and Slow Pointers pattern

1. Create a Dummy Node

Create a dummy node that points to head.
This simplifies handling the head swap — we don't need a special case for the first pair.
Set prev = dummy to track the node just before the current pair.

2. Iterate Through Pairs

Loop while prev.next and prev.next.next both exist (i.e., there's a full pair to swap).
Identify first = prev.next and second = first.next.

3. Swap the Pair

Set first.next = second.next — the first node now points past the pair.
Set second.next = first — the second node now points to the first.
Set prev.next = second — the previous node now points to what was the second node (now the new front of the pair).

4. Advance the Pointer

Move prev to first — after the swap, first is the second node in the pair, so it's the new "previous" for the next pair.

5. Return the Result

The new head is dummy.next.
Convert the list to an array and return it.

Key Insight

The dummy node technique eliminates edge cases for swapping the head.
Each swap involves exactly three pointer reassignments.

Time

O(n)we visit each node exactly once.

Space

O(1)only a constant number of pointer variables are used (excluding the output array).

Visualization

Input:

Linked List Traversal

—

Press play to start traversal

Slow (S)Fast (F)Both

4 steps

Solution Code

Odd Even Linked List

Add Two Numbers II