DSA sheet · Linked List · Reversal pattern

Swap Nodes in Pairs

This is the next problem in the reversal pattern. It is really "reverse the list, but only two nodes at a time". The teacher first pretends we don't know any linked list trick and solves it with an array copy (brute force). Then she shows the in-place way with a dummy node and three pointers: prev, first, second, where every swap is just three arrows changed in the right order. This problem is the warm-up for Reverse Nodes in k-Group, where the group size becomes k instead of 2.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

Part 0 · Linked lists from scratch (and the dummy node)
Part A · Brute force: copy values into a list, swap, write back
Part B · Optimal: swap the nodes in place with a dummy node
Part C · Revision page

Part 0 · Before starting

What is a linked list node?

A linked list is a chain of small boxes called nodes. Each node holds two things: a value (val) and a link to the next node (next). The last node's next is None, which means "the chain ends here".

given by LeetCode, don't write this in the solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # the number stored in this node
        self.next = next    # the next node, or None at the end

[1] → [2] → [3] → [4] → None
 ↑
head

head = the first node. It is the only door into the list. If you lose it, you lose the whole list.
None at the end = the stop sign. Every loop over a list stops when it reaches None.

Walking a list, and why there is no index

In an array you can jump straight to arr[3]. A linked list has no index. The nodes sit anywhere in memory, and the only way to find node 3 is to start at the head and follow the arrows one by one:

the basic walk

curr = head            # a helper pointer (an "alias"), head stays where it is
while curr is not None:
    print(curr.val)
    curr = curr.next   # step one arrow forward

So reaching position i costs O(i) steps, not O(1). That's why linked list problems are all about where you place your pointers.

Doubt: why use curr instead of just moving head?
→ The teacher repeats this in every video: never move head. If head walks forward, nobody remembers where the list starts, and you can't return it. Make a copy (curr) and walk with that.

Why you must save a link before you change it

Each node knows only its next node. If you overwrite a.next, the old next node is gone unless some other variable still points to it. So before rewiring an arrow, make sure every node you still need has a name. In this problem we name the nodes first and second before touching any arrow, and we change the arrows in an order that never loses a node.

The dummy node

A dummy node is a fake extra node we put in front of the head. Its value doesn't matter (we use 0).

[0] → [1] → [2] → [3] → [4] → None
 ↑     ↑
dummy head

Why bother? In this problem the head changes: after swapping, 2 comes first, not 1. Without a dummy, the first pair would need special code ("the new head is the second node"), while every other pair would be joined to the node before it. With the dummy, every pair, even the first one, has a node in front of it. So one piece of code works for all pairs, and at the end the real head is simply dummy.next.

Part A · Brute force: copy values, swap, write back

LeetCode 24 · Swap Nodes in Pairs

1The question in simple words

You get the head of a linked list. Take the nodes two at a time and swap each pair: 1st with 2nd, 3rd with 4th, and so on. Return the head of the new list.

Example 1 (even length)

before: [1] → [2] → [3] → [4] → None
after:  [2] → [1] → [4] → [3] → None
        new head = 2

Example 2 (odd length)

before: [1] → [2] → [3] → None
after:  [2] → [1] → [3] → None
        3 has no partner, it stays

The teacher's way to see it: treat each pair (1, 2) as a tiny list of its own and reverse it, so it becomes (2, 1). Then do the same for (3, 4). That's why it belongs to the reversal pattern.

Empty list

None → None

One node

[1] → None   (nothing to swap)

2What the constraints tell us

Number of nodes: 0 to 100 → 0 is allowed, so head can be None. We need a base case.
n ≤ 100 is tiny. TLE only starts at around 10⁸ to 10⁹ operations, so any approach works here.
The teacher's general rule for linked lists: almost every solution, brute force or optimal, is linear. The difference is usually how many passes (n vs 2n or more) and whether extra space is used.

Doubt: LeetCode says "don't change the values in the nodes". Is the brute force even allowed?
→ Not on LeetCode's strict reading. The brute force below swaps values, not nodes. The teacher shows it to build the thinking ("what would I do with an array?") and it does get accepted by the judge, but in an interview say clearly that it changes values, and then move to Part B, which really moves the nodes.

3Intuition: pretend it's an array

Forget linked lists for a moment. If the numbers were in a Python list, swapping pairs is easy: stand at index i, swap arr[i] with arr[i+1], then jump two places (i += 2) to the next pair.

index:  0   1   2   3
arr:   [1,  2,  3,  4]
        i→ swap      i (next jump) → swap

So the plan is: copy the list's values into an array, swap there, then copy the swapped values back into the same nodes.

4Building the logic

Step 1: fill the array

Start curr at head (not head itself, so we don't lose the list). Read curr.val, append it, move curr = curr.next. Stop when curr becomes None. For 1→2→3→4 we get [1, 2, 3, 4].

Step 2: swap in the array, how far should i go?

We use arr[i] and arr[i+1]. So i must stop at the second-last index, otherwise i+1 falls off the end. In the teacher's words, the loop runs while i < length − 1, stepping by 2.

length	i values (step 2, i < n−1)	pairs swapped
4	0, 2	(0,1), (2,3)
5	0, 2 (i = 4 is not < 4)	(0,1), (2,3); index 4 stays
1	none	nothing

The swap uses a temporary variable, just like swapping two glasses of juice with a third glass: temp = arr[i], arr[i] = arr[i+1], arr[i+1] = temp. (In Python you can also write arr[i], arr[i+1] = arr[i+1], arr[i].)

Step 3: write the values back

Start curr at head again. Walk the list and overwrite each node's value with the next number from the array: 2, 1, 4, 3. We didn't move any node, we only changed the numbers inside them. So the head node is still the first node, and we return head.

The base case

If the list is empty (head is None), return None. If it has just one node (head.next is None), there's no pair to swap, so return head as it is. Swapping only makes sense with at least two nodes.

5Approach steps

If head is None or head.next is None → return head.
Walk with curr, put every value into arr.
For i = 0, 2, 4, … while i < len(arr) − 1 → swap arr[i] and arr[i+1].
Walk again from head, write arr[0], arr[1], … into the nodes.
Return head.

6Code (Python)

Brute force: swap values with an array

class Solution:
    def swapPairs(self, head):
        if head is None or head.next is None:   # 0 or 1 node
            return head

        arr = []
        curr = head
        while curr is not None:                 # copy values out
            arr.append(curr.val)
            curr = curr.next

        for i in range(0, len(arr) - 1, 2):     # swap pairs in the array
            temp = arr[i]
            arr[i] = arr[i + 1]
            arr[i + 1] = temp

        curr = head
        idx = 0
        while curr is not None:                 # write values back
            curr.val = arr[idx]
            idx += 1
            curr = curr.next

        return head

7Code line by line

line	what it means
if head is None or head.next is None: return head	Empty list (allowed by the constraints) or a single node: nothing to swap.
curr = head	A walking copy. Head stays on the first node.
arr.append(curr.val) curr = curr.next	Copy one value, step forward. O(n) in total.
range(0, len(arr) - 1, 2)	i = 0, 2, 4, …, stopping before the last index so `i+1` always exists. Odd leftover stays.
temp = arr[i] … arr[i + 1] = temp	Classic three-line swap. About n/2 swaps.
curr.val = arr[idx]	Overwrite each node's number with the swapped order. No arrows change.
return head	The first node is still the first node (only its value changed).

8Dry run: 1 → 2 → 3 → 4

step	pointer / index	what changes	state after
1	curr = 1, 2, 3, 4, None	values appended	arr = [1, 2, 3, 4]
2	i = 0	swap arr[0], arr[1]	arr = [2, 1, 3, 4]
3	i = 2	swap arr[2], arr[3]	arr = [2, 1, 4, 3]
4	i = 4	4 < 3 is false → loop ends	arr = [2, 1, 4, 3]
5	curr = node A (was 1)	A.val = 2	[2] → [2] → [3] → [4]
6	curr = node B (was 2)	B.val = 1	[2] → [1] → [3] → [4]
7	curr = node C (was 3)	C.val = 4	[2] → [1] → [4] → [4]
8	curr = node D (was 4)	D.val = 3	[2] → [1] → [4] → [3] ✓

same boxes, new numbers:
 A     B     C     D
[2] → [1] → [4] → [3] → None
 ↑
head (still node A)

9Complexity & remember

Time O(n). The teacher counts it exactly: n to fill the array + n/2 swaps + n to write back = 5n/2. Still linear, but more than one pass.
Space O(n) for the extra array.

Remember the brute forceCopy out → swap arr[i], arr[i+1] with i += 2 → copy back. 5n/2 time, O(n) space, and it changes values, not nodes.

Part B · Optimal: swap the nodes in place

LeetCode 24 · O(1) extra space

1The question in simple words

Same question, but now the goal is to do it in place: no extra array. We change the arrows so the nodes themselves move. Node 2 really comes before node 1.

2What the constraints tell us

0 nodes is allowed, and the dummy node handles it with no special code (the loop just doesn't run and we return dummy.next = None).
The teacher's rule for linked lists: a single pass with no extra memory is "optimal". Two or more passes (2n, 3n…) or an extra array counts as brute force, even though both are linear.

3Intuition: three names and three arrows

To swap one pair we need to stand on three nodes:

[0] → [1] → [2] → [3] → [4] → None
 ↑     ↑     ↑
prev  first second

first and second: the two nodes we are swapping.
prev: the node just before the pair. Someone has to point to the pair from the left, and after the swap it must point to second instead of first. For the very first pair, that "someone" is the dummy node.

After the swap, the picture must be prev → second → first → (whatever came after second). That's three arrows to set. The whole skill is setting them in an order that never loses a node.

4Building the logic, arrow by arrow

The teacher builds the three lines slowly, looking at what each line does to the drawing. Let's follow the first pair (1, 2).

Arrow 1: first must skip over second

After the swap, 1 comes after 2, so 1 must point to whatever came after 2 (that's 3). Right now that node is reachable as second.next. So:

Line 1first.next = second.next

        ┌───────────┐
[0] → [1]   [2] → [3] → [4] → None
 ↑     ↑     ↑
prev  first second       (1 now points to 3; 2 still points to 3 too)

Now both 1 and 2 point to 3. Nothing is lost: 2 still has its name second.

Arrow 2: second must point back to first

Line 2second.next = first

[0] → [1] → [3] → [4] → None
       ↑
[2] ───┘          (2's arrow now points to 1)
 ↑
second            from 2 you read: 2 → 1 → 3 → 4
prev = 0, first = 1

So 2 → 1 → 3 → 4 is now correct. But the dummy still points to 1, so if we walked from the dummy we'd see 0 → 1 → 3 → 4 and miss 2.

Arrow 3: prev must point to the new front of the pair

Line 3prev.next = second

[0] → [2] → [1] → [3] → [4] → None
 ↑     ↑     ↑
prev second first

The first pair is swapped and joined to both sides: the dummy on the left, 3 on the right.

Move prev for the next pair

For pair (3, 4), the node right before it is now 1, which is first. So:

Line 4prev = first

[0] → [2] → [1] → [3] → [4] → None
             ↑     ↑     ↑
            prev  first second   (next round)

Doubt 1: what if I do line 2 first (second.next = first)?
→ Then 2's old arrow to 3 is overwritten, and nobody else points to 3. Node 3 and everything after it are lost. Line 1 copies second.next into first.next before that arrow is destroyed. This is the "save next before you change it" rule.

Doubt 2: why is first = prev.next and not first = head?
→ head is always node 1. In round two the pair is (3, 4), so first must be 3, which is prev.next after we moved prev to 1. Always find the pair relative to prev. And second = first.next (the same as prev.next.next).

When should the loop stop?

The teacher asks two "what if" questions:

What if 3 and 4 aren't there at all? prev is at 1, and prev.next is None. Nothing to swap → stop.
What if only 3 is there (odd length)? prev.next is 3, but prev.next.next is None. 3 has no partner, it must stay as it is → stop.

So we keep going only while both nodes of the next pair exist:

Loop conditionwhile prev.next is not None and prev.next.next is not None:

Doubt 3: could the check be in the other order, prev.next.next is not None and prev.next is not None?
→ No. If prev.next is None, reading .next on it crashes. and stops at the first False, so checking prev.next first protects the second check.

What do we return?

Not head. Head is still node 1, and after the swaps 1 is in second place. Returning head gives 1 → 4 → 3 and loses 2. The dummy always points to the real first node, so we return dummy.next.

5Approach steps

Make dummy = ListNode(0, head) and set prev = dummy.
While both prev.next and prev.next.next exist:
Name the pair: first = prev.next, second = first.next.
first.next = second.next (1 skips to 3).
second.next = first (2 points back to 1).
prev.next = second (the left side now sees 2).
prev = first (1 is now the node before the next pair).
After the loop, return dummy.next.

6Code (Python)

Optimal: in-place swap with a dummy node

class Solution:
    def swapPairs(self, head):
        dummy = ListNode(0, head)     # fake node in front of head
        prev = dummy                  # node just before the current pair

        while prev.next is not None and prev.next.next is not None:
            first = prev.next         # 1st node of the pair
            second = first.next       # 2nd node of the pair

            first.next = second.next  # first skips over second
            second.next = first       # second points back to first
            prev.next = second        # left side now points to second

            prev = first              # first is now the node before the next pair

        return dummy.next             # the real new head

7Code line by line

line	what it means
dummy = ListNode(0, head)	A fake node before the real head, so the first pair also has a "node before it". Builds 0 → 1 → 2 → 3 → 4.
prev = dummy	prev always stands one node behind the pair we're about to swap.
while prev.next is not None and prev.next.next is not None:	Swap only if two nodes are left. Stops for 0 left (even length) or 1 left (odd length).
first = prev.next second = first.next	Give names to the pair so no node gets lost while rewiring.
first.next = second.next	first now points past the pair. Must come before the next line.
second.next = first	The pair is reversed: second → first.
prev.next = second	Join the reversed pair back to the left part of the list.
prev = first	first is now the last node of the swapped pair, so it sits just before the next pair.
return dummy.next	The real head after swapping (node 2 here). Also returns None for an empty list.

8Dry run: 1 → 2 → 3 → 4 → 5 (odd length)

step	pointers	what changes	list after (from dummy)	answer so far
0	prev = 0	dummy created	0 → 1 → 2 → 3 → 4 → 5	—
1	prev 0, first 1, second 2	1.next = 3	0 → 1 → 3 … (2 → 3 too)
2	same	2.next = 1	0 → 1 → 3 → 4 → 5 (2 → 1 hidden)
3	same	0.next = 2	0 → 2 → 1 → 3 → 4 → 5	2 → 1
4	prev = 1	prev moves	same
5	prev 1, first 3, second 4	3.next = 5	0 → 2 → 1 → 3 → 5
6	same	4.next = 3	0 → 2 → 1 → 3 → 5 (4 → 3 hidden)
7	same	1.next = 4	0 → 2 → 1 → 4 → 3 → 5	2 → 1 → 4 → 3
8	prev = 3	prev moves	same
9	prev 3: prev.next = 5, prev.next.next = None	loop stops, 5 has no partner	0 → 2 → 1 → 4 → 3 → 5	return dummy.next = 2 → 1 → 4 → 3 → 5

snapshot after round 1

[0] → [2] → [1] → [3] → [4] → [5] → None
 ↑           ↑     ↑     ↑
dummy       prev  first second  (round 2 names)

snapshot after round 2

[0] → [2] → [1] → [4] → [3] → [5] → None
                         ↑     ↑
                        prev  prev.next.next = None → stop

With 1 → 2 → 3 → 4 the run is the same for two rounds, then prev sits on 3 and prev.next is None → stop, answer 2 → 1 → 4 → 3.

9Complexity & remember

Time O(n): one pass. Each round handles two nodes, so about n/2 rounds.
Space O(1): only a few pointers and one dummy node, no array.

Remember the in-place swapDummy in front, prev behind the pair. Loop while two nodes exist. Then first.next = second.next → second.next = first → prev.next = second → prev = first. Return dummy.next.

Part C · Revision page

	Brute force (array)	Optimal (in place)
what moves	values (nodes stay put)	the nodes themselves (arrows change)
extra memory	an array of n values	one dummy node + 3 pointers
passes	copy out + swap + copy back = 5n/2	one pass (n/2 rounds)
empty / 1 node	explicit base case	handled by the loop condition
return	`head`	`dummy.next`
time / space	O(n) / O(n)	O(n) / O(1)

If you remember only 5 lines 1. Each pair is a tiny list of 2 to reverse.
2. A dummy node gives the first pair a "prev" too.
3. Loop while prev.next and prev.next.next both exist.
4. Order: first.next = second.next, second.next = first, prev.next = second, prev = first.
5. Return dummy.next, never head.

Mistakes to avoid ✗ moving head instead of a helper pointer
✗ second.next = first before saving second.next (the rest of the list is lost)
✗ forgetting prev.next = second (the left side still points to first, a node vanishes)
✗ first = head inside the loop (always use prev.next)
✗ returning head (you lose the new first node)
✗ checking prev.next.next before prev.next (crash)

test it yourself (paste under either solution)

def build(vals):
    dummy = ListNode()
    tail = dummy
    for v in vals:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.swapPairs(build([1, 2, 3, 4]))))      # [2, 1, 4, 3]
print(to_list(s.swapPairs(build([1, 2, 3, 4, 5]))))   # [2, 1, 4, 3, 5]
print(to_list(s.swapPairs(build([1]))))               # [1]
print(to_list(s.swapPairs(build([]))))                # []

Based on this video: Swap Nodes in Pairs