Data Structures & Algorithms (DSA) Module 7 – Linked lists
Reversing linked lists and sublists
Reverse a singly linked list in place with three pointers, iteratively and recursively, then reverse a sublist between two positions and groups of k.
What you will learn
- Implement list reversal iteratively and recursively
- Implement the reversal of a sublist between two positions
- Implement the reversal of nodes in groups of k
- Check whether a list reads the same both ways and restore it afterwards
Before you start
What you’ll learn · Before you start
What you will learn
- Implement list reversal iteratively and recursively
- Implement the reversal of a sublist between two positions
- Implement the reversal of nodes in groups of k
- Check whether a list reads the same both ways and restore it afterwards
Before you start
On this page
Reversing a singly linked list means turning every next reference around, so that the old last node becomes the
head and the old head points at nothing. It takes one pass and three references: prev, the start of the part already
reversed; curr, the node being turned around; and nxt, saved before the turn because it is the only way to the
rest. That costs O(n) time and O(1) extra memory, and no node is copied or moved. A recursive version does the same
in fewer lines but keeps one call per node waiting, so it fails on long lists in Python. Sublists use the same step
with two reconnections at their ends. Reversing linked lists sounds like a puzzle, yet the step recurs: in groups of k,
in palindrome checks and in merge routines. This lesson traces the step on four nodes, then applies it to sublists.
Three references, one pass
Each pass of the loop does four things, always in this order: save the rest with nxt = curr.next, turn the current
node around with curr.next = prev, move the start of the reversed part with prev = curr, and step on with
curr = nxt. Swap the first two and the rest of the list is lost after one node. When curr becomes None, every
node has been turned, and prev is the new head.
The two halves of a reversal after two steps
Text description of the diagram
The list 1, 2, 3, 4 is being reversed in place, and two steps are done.
The reference prev points at the reversed part: node 2, whose next is node 1, whose next is None. The reference curr points at the untouched part: node 3, whose next is node 4, whose next is None. No node belongs to both parts, and no node is missing.
The dashed arrow shows the next step: after saving node 3's next, node 4, the step points node 3 back at node 2. Then prev moves to node 3 and curr to node 4, so the reversed part grows by one node and the untouched part shrinks by one.
The program below reverses 1 → 2 → 3 → 4 and prints both parts after every pass:
"""Reversing 1 -> 2 -> 3 -> 4 in place with three references, printing every pointer change."""
class Node:
__slots__ = ("value", "next")
def __init__(self, value, next=None):
self.value = value
self.next = next
def show(node):
out = []
while node is not None:
out.append(str(node.value))
node = node.next
return " -> ".join(out + ["None"])
head = None
for v in (4, 3, 2, 1):
head = Node(v, head)
print("start:", show(head))
prev, curr = None, head
step = 0
while curr is not None:
step += 1
nxt = curr.next # 1. save the rest of the list
curr.next = prev # 2. turn this node around
prev = curr # 3. the reversed part now starts here
curr = nxt # 4. move on to the untouched part
print(f"step {step}: turned {prev.value} around | reversed: {show(prev)} | untouched: {show(curr)}")
head = prev
print("result:", show(head))Output
start: 1 -> 2 -> 3 -> 4 -> None step 1: turned 1 around | reversed: 1 -> None | untouched: 2 -> 3 -> 4 -> None step 2: turned 2 around | reversed: 2 -> 1 -> None | untouched: 3 -> 4 -> None step 3: turned 3 around | reversed: 3 -> 2 -> 1 -> None | untouched: 4 -> None step 4: turned 4 around | reversed: 4 -> 3 -> 2 -> 1 -> None | untouched: None result: 4 -> 3 -> 2 -> 1 -> None
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 reverse_trace.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Read the two parts column by column: the reversed part grows by one node per step and the untouched part shrinks by
one, and together they always hold all four nodes. That observation is the loop’s invariant. Every node’s next is
written exactly once, so the work is n assignments of next for n nodes, the least any reversal can do.
| Operation | Time | Extra space | Note |
|---|---|---|---|
| The three-pointer loop | O(n) | O(1) | one pass, nothing copied |
| The recursive version | O(n) | O(n) | one waiting call per node |
| A sublist of m nodes at position left | O(left + m) | O(1) | walk to it, reverse it |
| Groups of k | O(n) | O(1) | each node is counted once and turned once |
The recursive version reverses the rest of the list first and then hangs the current node behind its old successor.
All n calls wait at once, and CPython stops a recursion at sys.getrecursionlimit(), 1,000 frames by default, with
a RecursionError. The recursion lesson covers those limits; for reversing
linked lists of unknown length, use the loop.
Sublists: reverse the middle, reconnect both ends
To reverse only the nodes at positions left to right, walk to the node just before the sublist, reverse exactly
right − left + 1 nodes with the same step, and reconnect both ends. The node before the sublist must point at the
old last node of the sublist, and the old first node, now the last, must point at whatever followed the sublist. A
dummy node in front of the head gives a sublist that starts at position 1 a node before it too, so no branch is
needed.
"""Reverse only the nodes at positions left to right (counted from 1), with a dummy node in front of the head."""
class Node:
__slots__ = ("value", "next")
def __init__(self, value, next=None):
self.value = value
self.next = next
def build(values):
head = None
for v in reversed(values):
head = Node(v, head)
return head
def values_of(node):
out = []
while node is not None:
out.append(node.value)
node = node.next
return out
def reverse_between(head, left, right):
dummy = Node(None, head)
before = dummy
for _ in range(left - 1): # 1. stop on the node before the sublist
before = before.next
first = before.next # this node will end the reversed sublist
prev, curr = None, first
for _ in range(right - left + 1): # 2. reverse exactly right - left + 1 nodes
nxt = curr.next
curr.next = prev
prev, curr = curr, nxt
before.next = prev # 3. reconnect the front: before -> the old last node of the sublist
first.next = curr # 4. reconnect the back: the old first node -> the rest of the list
return dummy.next
for values, left, right in [([1, 2, 3, 4, 5, 6], 2, 5), ([1, 2, 3, 4, 5, 6], 1, 3), ([1, 2, 3, 4, 5, 6], 4, 6), ([7, 8], 1, 2), ([9], 1, 1)]:
result = values_of(reverse_between(build(values), left, right))
print(f"reverse positions {left}..{right} of {values}: {result}")Output
reverse positions 2..5 of [1, 2, 3, 4, 5, 6]: [1, 5, 4, 3, 2, 6] reverse positions 1..3 of [1, 2, 3, 4, 5, 6]: [3, 2, 1, 4, 5, 6] reverse positions 4..6 of [1, 2, 3, 4, 5, 6]: [1, 2, 3, 6, 5, 4] reverse positions 1..2 of [7, 8]: [8, 7] reverse positions 1..1 of [9]: [9]
Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 reverse_between.py
Runs on this device, in your browser. The first run downloads Python (about 13.5 MB), which is kept for the next runs.
Your run, in this browser
Five cases cover the positions that break carelessly written code: a sublist in the middle, at the front, at the end, the whole list, and a single node. Groups of k are sublists one after another: count k nodes first, reverse them, reconnect, and move on, leaving a final group shorter than k as it is unless the specification says otherwise. The same building block serves palindrome checks: locate the midpoint with a slow and a fast pointer, turn the back half around, compare the halves node by node, then turn the back half around again.
Practise: groups of k
Reverse a list in groups of k, keeping a short final group in its order. The sample tests check every k from 1 to 9 on random lists against a model, and that you relink the nodes you were given rather than building new ones.
Exercise · Medium · Python, JavaScript
Reverse a linked list in groups of k nodes
Write reverse_k_group(head, k) (in JavaScript reverseKGroup(head, k)): reverse the nodes of a singly linked list in groups of k, from the front, and return the new head. A final group with fewer than k nodes keeps its order. Relink the nodes you are given; do not create new ones or change their values. k is at least 1.
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8withk = 3becomes3 → 2 → 1 → 6 → 5 → 4 → 7 → 8.- With
k = 1the list is unchanged, and withkequal to the length it is fully reversed. - An empty list (
None, in JavaScriptnull) stays empty.
The nodes are ListNode objects with val and next, defined in the starter file. The sample tests check the examples, every k from 1 to 9 on lists of up to 30 nodes against a model, and that the nodes you return are the nodes you were given.
Python · Starter code · reverse_groups.py
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
def reverse_k_group(head, k):
"""Reverse the nodes in groups of k from the front; a final shorter group keeps its order. Returns the new head."""
return headThe sample tests · test_reverse_groups.py
import random
from reverse_groups import ListNode, reverse_k_group
def build(values):
head = None
for v in reversed(values):
head = ListNode(v, head)
return head
def nodes_of(head):
out = []
while head is not None:
out.append(head)
head = head.next
assert len(out) <= 1_000, "the nodes loop back on themselves"
return out
def values_of(head):
return [n.val for n in nodes_of(head)]
def model(values, k):
"""Plainly right: reverse each full chunk of k values; a shorter last chunk keeps its order."""
out = []
for i in range(0, len(values), k):
chunk = values[i : i + k]
out += chunk[::-1] if len(chunk) == k else chunk
return out
def test_groups_of_three():
"""the example: eight nodes in groups of 3"""
assert values_of(reverse_k_group(build([1, 2, 3, 4, 5, 6, 7, 8]), 3)) == [3, 2, 1, 6, 5, 4, 7, 8]
def test_k_one_and_k_length():
"""k = 1 changes nothing, k = the length reverses everything"""
assert values_of(reverse_k_group(build([1, 2, 3, 4]), 1)) == [1, 2, 3, 4]
assert values_of(reverse_k_group(build([1, 2, 3, 4]), 4)) == [4, 3, 2, 1]
def test_k_longer_than_the_list():
"""a list shorter than k keeps its order"""
assert values_of(reverse_k_group(build([1, 2, 3]), 5)) == [1, 2, 3]
def test_empty_and_single():
"""an empty list stays empty, and a single node stays"""
assert reverse_k_group(None, 2) is None
assert values_of(reverse_k_group(build([7]), 2)) == [7]
def test_exact_multiple():
"""six nodes in groups of 2: every group is complete"""
assert values_of(reverse_k_group(build([1, 2, 3, 4, 5, 6]), 2)) == [2, 1, 4, 3, 6, 5]
def test_nodes_are_reused():
"""the result holds exactly the nodes that were given, each once, with their values unchanged"""
head = build(list(range(10)))
given = {id(n): n.val for n in nodes_of(head)}
result = nodes_of(reverse_k_group(head, 3))
assert len(result) == 10
assert {id(n) for n in result} == set(given)
assert all(given[id(n)] == n.val for n in result)
def test_against_the_model():
"""every k from 1 to 9 on random lists of 0 to 30 nodes"""
rng = random.Random(9)
for _ in range(300):
values = [rng.randint(0, 99) for _ in range(rng.randint(0, 30))]
for k in range(1, 10):
assert values_of(reverse_k_group(build(values), k)) == model(values, k), (values, k)JavaScript · Starter code · reverse_groups.mjs
export class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
/** Reverse the nodes in groups of k from the front; a final shorter group keeps its order. Returns the new head. */
export function reverseKGroup(head, k) {
return head;
}The sample tests · reverse_groups.test.mjs
import { test, assert } from 'mysmartcopilot:test';
import { ListNode, reverseKGroup } from './reverse_groups.mjs';
function build(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) head = new ListNode(values[i], head);
return head;
}
function nodesOf(head) {
const out = [];
for (let n = head; n !== null && n !== undefined; n = n.next) {
out.push(n);
if (out.length > 1000) throw new Error('the nodes loop back on themselves');
}
return out;
}
const valuesOf = (head) => nodesOf(head).map((n) => n.val);
/** Plainly right: reverse each full chunk of k values; a shorter last chunk keeps its order. */
function model(values, k) {
const out = [];
for (let i = 0; i < values.length; i += k) {
const chunk = values.slice(i, i + k);
out.push(...(chunk.length === k ? chunk.reverse() : chunk));
}
return out;
}
let seed = 9;
const random = () => (seed = (seed * 48271) % 2147483647) / 2147483647;
const randint = (lo, hi) => lo + Math.floor(random() * (hi - lo + 1));
test('the example: eight nodes in groups of 3', () => {
assert.deepEqual(valuesOf(reverseKGroup(build([1, 2, 3, 4, 5, 6, 7, 8]), 3)), [3, 2, 1, 6, 5, 4, 7, 8]);
});
test('k = 1 changes nothing, k = the length reverses everything', () => {
assert.deepEqual(valuesOf(reverseKGroup(build([1, 2, 3, 4]), 1)), [1, 2, 3, 4]);
assert.deepEqual(valuesOf(reverseKGroup(build([1, 2, 3, 4]), 4)), [4, 3, 2, 1]);
});
test('a list shorter than k keeps its order', () => {
assert.deepEqual(valuesOf(reverseKGroup(build([1, 2, 3]), 5)), [1, 2, 3]);
});
test('an empty list stays empty, and a single node stays', () => {
assert.equal(reverseKGroup(null, 2), null);
assert.deepEqual(valuesOf(reverseKGroup(build([7]), 2)), [7]);
});
test('six nodes in groups of 2: every group is complete', () => {
assert.deepEqual(valuesOf(reverseKGroup(build([1, 2, 3, 4, 5, 6]), 2)), [2, 1, 4, 3, 6, 5]);
});
test('the result holds exactly the nodes that were given, each once, with their values unchanged', () => {
const given = nodesOf(build(Array.from({ length: 10 }, (_, i) => i)));
const values = new Map(given.map((n) => [n, n.val]));
const result = nodesOf(reverseKGroup(given[0], 3));
assert.equal(result.length, 10);
assert.ok(result.every((n) => values.has(n) && values.get(n) === n.val));
assert.equal(new Set(result).size, 10);
});
test('every k from 1 to 9 on random lists of 0 to 30 nodes', () => {
for (let t = 0; t < 300; t++) {
const values = Array.from({ length: randint(0, 30) }, () => randint(0, 99));
for (let k = 1; k <= 9; k++) assert.deepEqual(valuesOf(reverseKGroup(build(values), k)), model(values, k), `k = ${k}`);
}
});A hint
Use a dummy node in front of the head and keep before, the node in front of the next group. Before reversing a group, walk k nodes from before.next to check that the group is complete. Reverse those k nodes with the three-pointer step, then reconnect: before.next becomes the group's old last node, and the group's old first node points at the rest of the list and becomes the new before.
Results of the sample tests
| Test | Result | Details |
|---|
What your code printed
The sample tests run on this device, in your browser (Pyodide, QuickJS): nothing is sent to mysmartcopilot.com. The first run of each language downloads it: Python (about 13.5 MB) or JavaScript (about 0.6 MB), which is kept for the next runs. A check in your browser is feedback for you, not proof that the code is right for every input.
Check yourself
5 questions about this lesson. Every answer and why it is right is on the page, behind “Show the answer”. Your score stays in this browser.
The reversal's invariant, proved, and the loop in four more languages Pro: opens with a Pro, Premium or Ultimate pass
The loop is short enough to get right by luck and to get wrong by one swapped line. This part states the invariant that makes it correct, proves that each pass keeps it and that the loop ends with the reversed list, and runs the same loop in JavaScript, Java, C++ and Go, where the language decides how the three assignments may be written.
In this part:
- The invariant, and the proof that no node is lost
- Three slips, and what each one does to 1 → 2 → 3
- The same loop in JavaScript, Java, C++ and Go
3 runnable examples (C++, Go, Java, JavaScript, reverse_session.py, session.py) · about 3 minutes
Opening this part with your pass…
This part opens with any MySmartCoPilot pass.
- Pro pass · 1 week₹79$2.99
- 30 days₹179$5.99
- 1 year₹1,699$45
One payment; a pass never renews. The price shown is the total you pay: no fees or charges are added at checkout.
Passes can’t be bought right now, so this part can’t be opened at the moment. The free part above stands on its own. If you have a pass, enter your licence key.
It also opens every other in-depth part in Learn and every Pro tool. Sales are final, except where the law gives you a right to withdraw, for example in the EU and the UK (refund policy).
Recursive reversal and the stack, measured Pro: opens with a Pro, Premium or Ultimate pass
The recursive reversal is a favourite in interviews because it is elegant and because its failure is easy to explain once measured. This part shows how it works, finds the longest list it can reverse under Python’s default limit, and compares four ways to reverse a list on time, memory and risk.
In this part:
- How the recursive version turns the list around
- Measured: where the recursive version stops
- Four ways to reverse, compared
1 runnable example (Python) · about 2 minutes
Opening this part with your pass…Pro part. It opens with the same pass as the part above.
Sublists, groups of k and palindromes: dry runs, edge cases and a practice set Pro: opens with a Pro, Premium or Ultimate pass
Reversing part of a list is where off-by-one errors live: a group counted wrong, a reconnection forgotten, a short final group reversed by mistake. The groups of k are traced step by step, the palindrome check restores the list it inspects, and a list of boundary inputs and a few worked questions close the part.
In this part:
- A dry run of groups of k, with the count that protects the short tail
- Palindromes: reverse half, compare, and put it back
- Edge cases to test before you submit
- A practice set with answers
2 runnable examples (Python) · about 3 minutes
Opening this part with your pass…Pro part. It opens with the same pass as the part above.
Interview questions
-
Mid to senior
A teammate defends a recursive list reversal because it is "tail recursive": each call ends with the recursive call. On a list of a million nodes, is it safe in Python, Java, C++ built with clang -O2, and Scheme? How would you make sure in each?
-
Fresher to mid
Reverse the nodes between positions left and right of a singly linked list in one pass. Walk through 1 → 2 → 3 → 4 → 5 with left = 2 and right = 4, name every pointer you change, and say which inputs break code that has no dummy node.
-
Mid to senior
How do you reverse a doubly linked list with head and tail sentinels in place, and which links do candidates usually forget? Then explain how a list class could offer reversal in O(1) time, and what that costs every other operation.
Key takeaways
- Reverse a list with three references, saving
nextbefore turningcurraround; it is O(n) time and O(1) memory. - The recursive version keeps a waiting call per node and stops at Python’s recursion limit, 1,000 frames by default.
- To reverse a sublist, stop on the node before it, reverse exactly its nodes, then reconnect both ends.
- Groups of k are consecutive sublists; count each group before reversing it so that a short final group stays as it is.
References
- sys.getrecursionlimit and sys.setrecursionlimit (The Python Standard Library) (Python Software Foundation)
- RecursionError (Built-in Exceptions) (Python Software Foundation)
- The Python Language Reference: assignment statements (Python Software Foundation)
- The Go Programming Language Specification: assignment statements (The Go Authors)
- LinkedList (Java SE 25 API) (Oracle)
- Dictionary of Algorithms and Data Structures (National Institute of Standards and Technology (NIST))
Related tools
Report a problem with this lesson
Kept only in this browser. Your Learn progress