11.06Beginner / Intermediate5 topics18 min5 interactive animations

Reversal variants

Reversal variants of the three-pointer technique: full reversal (iterative and recursive), reversing a range, reversing in groups of k and the reorder-list pattern that combines middle, reverse and merge.

Learning goals

Reverse iteratively and recursively
Reverse a sub-range with a dummy node
Reverse nodes in groups of k
Reorder a list by splicing two halves

Prerequisites

Singly linked operationsFast and slow pointers

11.06.1

Full reverse

Iterative reversal keeps prev, curr and next: save curr.next, point curr.next at prev, advance both. It runs in O(n) time and O(1) space. The new head is the old tail, which is where prev ends.

Watch each arrow flip in the animation.

Java

1static Node reverse(Node head) {
2    Node prev = null, curr = head;
3    while (curr != null) {
4        Node next = curr.next;
5        curr.next = prev;
6        prev = curr; curr = next;
7    }
8    return prev;
9}

Reversing a linked list by flipping pointers

Interactive · edit the input

linked list · 5 nodes

null

head

Node being flippedAlready reversed

Setup

Reversal flips every next pointer. No values move: only the arrows change, in O(n) time and O(1) space.

Step 1 / 17

Java

1static Node reverse(Node head) {
2    Node prev = null, curr = head;
3    while (curr != null) {
4        Node next = curr.next;          // save the rest of the list
5        curr.next = prev;               // flip the pointer
6        prev = curr; curr = next;       // step forward
7    }
8    return prev;                        // prev is the new head
9}
10static Node reverseBetween(Node head, int left, int right) {      // 1-based positions
11    Node dummy = new Node(0); dummy.next = head; Node pre = dummy;
12    for (int i = 1; i < left; i++) pre = pre.next;                // node before the segment
13    Node curr = pre.next;
14    for (int i = 0; i < right - left; i++) {
15        Node next = curr.next;
16        curr.next = next.next; next.next = pre.next; pre.next = next;   // move next to the front of the segment
17    }
18    return dummy.next;
19}
20static Node reverseKGroup(Node head, int k) {                     // groups shorter than k stay as they are
21    Node dummy = new Node(0); dummy.next = head; Node groupPrev = dummy;
22    while (true) {
23        Node kth = groupPrev; for (int i = 0; i < k && kth != null; i++) kth = kth.next;
24        if (kth == null) break;                                   // fewer than k nodes left
25        Node groupStart = groupPrev.next, groupNext = kth.next, prev = groupNext, curr = groupStart;
26        while (curr != groupNext) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }
27        groupPrev.next = kth; groupPrev = groupStart;
28    }
29    return dummy.next;
30}

Live state

head

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L2	head=1	Reversal flips every next pointer. No values move: only the arrows change, in O(n) time and O(1) space.
2	L4	head=1	Save next = 2 before changing curr.next, or the rest of the list would be lost.
3	L5	head=1	curr.next = prev: node 1 now points to null (it becomes the tail).
4	L6	head=1	Step both pointers forward.
5	L4	head=1	Save next = 3 before changing curr.next, or the rest of the list would be lost.
6	L5	head=1	curr.next = prev: node 2 now points back at 1.
7	L6	head=1	Step both pointers forward.
8	L4	head=1	Save next = 4 before changing curr.next, or the rest of the list would be lost.
9	L5	head=1	curr.next = prev: node 3 now points back at 2.
10	L6	head=1	Step both pointers forward.
11	L4	head=1	Save next = 5 before changing curr.next, or the rest of the list would be lost.
12	L5	head=1	curr.next = prev: node 4 now points back at 3.
13	L6	head=1	Step both pointers forward.
14	L4	head=1	Save next = null before changing curr.next, or the rest of the list would be lost.
15	L5	head=1	curr.next = prev: node 5 now points back at 4.
16	L6	head=1	Step both pointers forward.
17	L8	head=5 return=[5, 4, 3, 2, 1]	Return prev as the new head: [5, 4, 3, 2, 1].

11.06.2

Reverse recursively

The recursive version reverses everything after the head and then makes the head's successor point back to the head. The base case is an empty or single-node list. It is short but uses O(n) call-stack space, so very long lists risk StackOverflowError; prefer the iterative version for large inputs.

The iterative version in the animation does the same relinking without the recursion.

Java

1static Node reverseRecursive(Node head) {
2    if (head == null || head.next == null) return head;
3    Node newHead = reverseRecursive(head.next);   // reverse the rest
4    head.next.next = head;                        // the old successor now points back at head
5    head.next = null;                             // head becomes the tail
6    return newHead;
7}

Reversing a linked list by flipping pointers

Interactive · edit the input

linked list · 5 nodes

null

head

Node being flippedAlready reversed

Setup

Reversal flips every next pointer. No values move: only the arrows change, in O(n) time and O(1) space.

Step 1 / 17

Java

1static Node reverse(Node head) {
2    Node prev = null, curr = head;
3    while (curr != null) {
4        Node next = curr.next;          // save the rest of the list
5        curr.next = prev;               // flip the pointer
6        prev = curr; curr = next;       // step forward
7    }
8    return prev;                        // prev is the new head
9}
10static Node reverseBetween(Node head, int left, int right) {      // 1-based positions
11    Node dummy = new Node(0); dummy.next = head; Node pre = dummy;
12    for (int i = 1; i < left; i++) pre = pre.next;                // node before the segment
13    Node curr = pre.next;
14    for (int i = 0; i < right - left; i++) {
15        Node next = curr.next;
16        curr.next = next.next; next.next = pre.next; pre.next = next;   // move next to the front of the segment
17    }
18    return dummy.next;
19}
20static Node reverseKGroup(Node head, int k) {                     // groups shorter than k stay as they are
21    Node dummy = new Node(0); dummy.next = head; Node groupPrev = dummy;
22    while (true) {
23        Node kth = groupPrev; for (int i = 0; i < k && kth != null; i++) kth = kth.next;
24        if (kth == null) break;                                   // fewer than k nodes left
25        Node groupStart = groupPrev.next, groupNext = kth.next, prev = groupNext, curr = groupStart;
26        while (curr != groupNext) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }
27        groupPrev.next = kth; groupPrev = groupStart;
28    }
29    return dummy.next;
30}

Live state

head

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L2	head=1	Reversal flips every next pointer. No values move: only the arrows change, in O(n) time and O(1) space.
2	L4	head=1	Save next = 2 before changing curr.next, or the rest of the list would be lost.
3	L5	head=1	curr.next = prev: node 1 now points to null (it becomes the tail).
4	L6	head=1	Step both pointers forward.
5	L4	head=1	Save next = 3 before changing curr.next, or the rest of the list would be lost.
6	L5	head=1	curr.next = prev: node 2 now points back at 1.
7	L6	head=1	Step both pointers forward.
8	L4	head=1	Save next = 4 before changing curr.next, or the rest of the list would be lost.
9	L5	head=1	curr.next = prev: node 3 now points back at 2.
10	L6	head=1	Step both pointers forward.
11	L4	head=1	Save next = 5 before changing curr.next, or the rest of the list would be lost.
12	L5	head=1	curr.next = prev: node 4 now points back at 3.
13	L6	head=1	Step both pointers forward.
14	L4	head=1	Save next = null before changing curr.next, or the rest of the list would be lost.
15	L5	head=1	curr.next = prev: node 5 now points back at 4.
16	L6	head=1	Step both pointers forward.
17	L8	head=5 return=[5, 4, 3, 2, 1]	Return prev as the new head: [5, 4, 3, 2, 1].

11.06.3

Reverse between indices

To reverse only positions left through right (1-based), walk to the node before the segment (pre, using a dummy head when left is 1), then repeatedly move the node after curr to the front of the segment: curr.next = next.next; next.next = pre.next; pre.next = next. It is one pass, O(n), and the rest of the list stays linked.

Choose Reverse positions left..right and try 2..4.

Java

1static Node reverseBetween(Node head, int left, int right) {
2    Node dummy = new Node(0); dummy.next = head;
3    Node pre = dummy;
4    for (int i = 1; i < left; i++) pre = pre.next;
5    Node curr = pre.next;
6    for (int i = 0; i < right - left; i++) {
7        Node next = curr.next;
8        curr.next = next.next;
9        next.next = pre.next;
10        pre.next = next;
11    }
12    return dummy.next;
13}

Reversing a linked list by flipping pointers

Interactive · edit the input

linked list · 5 nodes

null

head

Node being flippedAlready reversed

Setup

Reversal flips every next pointer. No values move: only the arrows change, in O(n) time and O(1) space.

Step 1 / 17

Java

1static Node reverse(Node head) {
2    Node prev = null, curr = head;
3    while (curr != null) {
4        Node next = curr.next;          // save the rest of the list
5        curr.next = prev;               // flip the pointer
6        prev = curr; curr = next;       // step forward
7    }
8    return prev;                        // prev is the new head
9}
10static Node reverseBetween(Node head, int left, int right) {      // 1-based positions
11    Node dummy = new Node(0); dummy.next = head; Node pre = dummy;
12    for (int i = 1; i < left; i++) pre = pre.next;                // node before the segment
13    Node curr = pre.next;
14    for (int i = 0; i < right - left; i++) {
15        Node next = curr.next;
16        curr.next = next.next; next.next = pre.next; pre.next = next;   // move next to the front of the segment
17    }
18    return dummy.next;
19}
20static Node reverseKGroup(Node head, int k) {                     // groups shorter than k stay as they are
21    Node dummy = new Node(0); dummy.next = head; Node groupPrev = dummy;
22    while (true) {
23        Node kth = groupPrev; for (int i = 0; i < k && kth != null; i++) kth = kth.next;
24        if (kth == null) break;                                   // fewer than k nodes left
25        Node groupStart = groupPrev.next, groupNext = kth.next, prev = groupNext, curr = groupStart;
26        while (curr != groupNext) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }
27        groupPrev.next = kth; groupPrev = groupStart;
28    }
29    return dummy.next;
30}

Live state

head

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L2	head=1	Reversal flips every next pointer. No values move: only the arrows change, in O(n) time and O(1) space.
2	L4	head=1	Save next = 2 before changing curr.next, or the rest of the list would be lost.
3	L5	head=1	curr.next = prev: node 1 now points to null (it becomes the tail).
4	L6	head=1	Step both pointers forward.
5	L4	head=1	Save next = 3 before changing curr.next, or the rest of the list would be lost.
6	L5	head=1	curr.next = prev: node 2 now points back at 1.
7	L6	head=1	Step both pointers forward.
8	L4	head=1	Save next = 4 before changing curr.next, or the rest of the list would be lost.
9	L5	head=1	curr.next = prev: node 3 now points back at 2.
10	L6	head=1	Step both pointers forward.
11	L4	head=1	Save next = 5 before changing curr.next, or the rest of the list would be lost.
12	L5	head=1	curr.next = prev: node 4 now points back at 3.
13	L6	head=1	Step both pointers forward.
14	L4	head=1	Save next = null before changing curr.next, or the rest of the list would be lost.
15	L5	head=1	curr.next = prev: node 5 now points back at 4.
16	L6	head=1	Step both pointers forward.
17	L8	head=5 return=[5, 4, 3, 2, 1]	Return prev as the new head: [5, 4, 3, 2, 1].

11.06.4

Reverse in k-groups

Reverse each consecutive group of k nodes and leave a final group shorter than k unchanged. For each group first check that k nodes remain, reverse the group with the usual three pointers (making the first node point at the node after the group), then reconnect the previous group to the new group head. O(n) time, O(1) space.

Try groups of 2 and groups of 3 on the presets.

Java

1static Node reverseKGroup(Node head, int k) {
2    Node dummy = new Node(0); dummy.next = head;
3    Node groupPrev = dummy;
4    while (true) {
5        Node kth = groupPrev;
6        for (int i = 0; i < k && kth != null; i++) kth = kth.next;
7        if (kth == null) break;                                   // fewer than k nodes remain
8        Node groupStart = groupPrev.next, groupNext = kth.next, prev = groupNext, curr = groupStart;
9        while (curr != groupNext) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }
10        groupPrev.next = kth;
11        groupPrev = groupStart;
12    }
13    return dummy.next;
14}

Reversing a linked list by flipping pointers

Interactive · edit the input

linked list · 5 nodes

null

head

Node being flippedAlready reversed

Setup

Reversal flips every next pointer. No values move: only the arrows change, in O(n) time and O(1) space.

Step 1 / 17

Java

1static Node reverse(Node head) {
2    Node prev = null, curr = head;
3    while (curr != null) {
4        Node next = curr.next;          // save the rest of the list
5        curr.next = prev;               // flip the pointer
6        prev = curr; curr = next;       // step forward
7    }
8    return prev;                        // prev is the new head
9}
10static Node reverseBetween(Node head, int left, int right) {      // 1-based positions
11    Node dummy = new Node(0); dummy.next = head; Node pre = dummy;
12    for (int i = 1; i < left; i++) pre = pre.next;                // node before the segment
13    Node curr = pre.next;
14    for (int i = 0; i < right - left; i++) {
15        Node next = curr.next;
16        curr.next = next.next; next.next = pre.next; pre.next = next;   // move next to the front of the segment
17    }
18    return dummy.next;
19}
20static Node reverseKGroup(Node head, int k) {                     // groups shorter than k stay as they are
21    Node dummy = new Node(0); dummy.next = head; Node groupPrev = dummy;
22    while (true) {
23        Node kth = groupPrev; for (int i = 0; i < k && kth != null; i++) kth = kth.next;
24        if (kth == null) break;                                   // fewer than k nodes left
25        Node groupStart = groupPrev.next, groupNext = kth.next, prev = groupNext, curr = groupStart;
26        while (curr != groupNext) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }
27        groupPrev.next = kth; groupPrev = groupStart;
28    }
29    return dummy.next;
30}

Live state

head

No condition evaluated on this step

Execution trace (dry run table)Show 17 steps

Step	Line	State	What happens
1	L2	head=1	Reversal flips every next pointer. No values move: only the arrows change, in O(n) time and O(1) space.
2	L4	head=1	Save next = 2 before changing curr.next, or the rest of the list would be lost.
3	L5	head=1	curr.next = prev: node 1 now points to null (it becomes the tail).
4	L6	head=1	Step both pointers forward.
5	L4	head=1	Save next = 3 before changing curr.next, or the rest of the list would be lost.
6	L5	head=1	curr.next = prev: node 2 now points back at 1.
7	L6	head=1	Step both pointers forward.
8	L4	head=1	Save next = 4 before changing curr.next, or the rest of the list would be lost.
9	L5	head=1	curr.next = prev: node 3 now points back at 2.
10	L6	head=1	Step both pointers forward.
11	L4	head=1	Save next = 5 before changing curr.next, or the rest of the list would be lost.
12	L5	head=1	curr.next = prev: node 4 now points back at 3.
13	L6	head=1	Step both pointers forward.
14	L4	head=1	Save next = null before changing curr.next, or the rest of the list would be lost.
15	L5	head=1	curr.next = prev: node 5 now points back at 4.
16	L6	head=1	Step both pointers forward.
17	L8	head=5 return=[5, 4, 3, 2, 1]	Return prev as the new head: [5, 4, 3, 2, 1].

11.06.5

Reorder list

Reorder L0 → L1 → … → Ln into L0 → Ln → L1 → Ln-1 → …: find the middle, cut the list there, reverse the second half and weave the two halves together by alternating nodes. Each step is O(n), so the whole is O(n) time and O(1) space.

Switch the animation to Reorder and watch the second half being reversed and then interleaved.

Java

1static void reorder(Node head) {
2    Node slow = head, fast = head;
3    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
4    Node prev = null, curr = slow.next; slow.next = null;          // cut after the first half
5    while (curr != null) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }
6    for (Node a = head, b = prev; b != null; ) {                    // weave
7        Node an = a.next, bn = b.next;
8        a.next = b; b.next = an;
9        a = an; b = bn;
10    }
11}

Palindrome list and reorder list (middle, reverse, combine)

Interactive · edit the input

linked list · 5 nodes

null

head

slow

fast

slow / compared nodefast / second halfMatching pairMismatch

Setup

Plan: find the middle, reverse the second half in place, then compare the two halves from the outside in. O(n) time, O(1) space.

Step 1 / 11

Java

1static boolean isPalindrome(Node head) {
2    Node slow = head, fast = head;
3    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }   // slow = middle
4    Node prev = null, curr = slow;
5    while (curr != null) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }   // reverse the second half
6    for (Node a = head, b = prev; b != null; a = a.next, b = b.next)
7        if (a.val != b.val) return false;
8    return true;                                   // callers that still need the list should re-reverse the second half
9}
10static void reorder(Node head) {                   // L0 L1 ... Ln  ->  L0 Ln L1 Ln-1 ...
11    Node slow = head, fast = head;
12    while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }
13    Node prev = null, curr = slow.next; slow.next = null;     // cut after the first half
14    while (curr != null) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; }
15    for (Node a = head, b = prev; b != null; ) {              // weave the two halves together
16        Node an = a.next, bn = b.next; a.next = b; b.next = an; a = an; b = bn;
17    }
18}

Live state

No condition evaluated on this step

Execution trace (dry run table)Show 11 steps

Step	Line	State	What happens
1	L2		Plan: find the middle, reverse the second half in place, then compare the two halves from the outside in. O(n) time, O(1) space.
2	L3	slow=2 fast=3	slow = 2, fast = 3.
3	L3	slow=3 fast=1	slow = 3, fast = 1.
4	L4		Reverse the second half with the usual three-pointer loop.
5	L5		Flip 3 to point at null.
6	L5		Flip 2 to point at 3.
7	L5		Flip 1 to point at 2.
8	L7	a=1 b=1	1 = 1: the outer pair matches.
9	L7	a=2 b=2	2 = 2: the outer pair matches.
10	L7	a=3 b=3	3 = 3: the outer pair matches.
11	L8	return=true	Every pair matched: the list is a palindrome. (The second half is still reversed; undo that if the list is used again.)

Practice ladder

Now try it yourself

Easy

Reverse 1 → 2 → 3 → 4 by hand
What is the base case of the recursive reversal?

Medium

Reverse positions 2 to 4 of 1 → 2 → 3 → 4 → 5
Reverse 1 → 2 → 3 → 4 → 5 in groups of 2

Advanced

Reverse alternate groups of k nodes

Key takeaways

prev, curr, next: save the successor, flip the arrow, advance.
A dummy head removes the left = 1 special case.
Reorder = middle + reverse + weave, all in O(n) time and O(1) space.