These are the notes for DSA episode 21, the first episode of the linked list block. We build a linked list from scratch (a train of coaches, each hooked to the next), then solve the most asked linked list question of all: reverse it. The obvious way, unhooking the last coach again and again, is O(n²) and times out on 2 lakh nodes. One idea fixes it: walk once and flip every arrow with three pointers, prev, curr and next: O(n) time, O(1) space. We also write the recursive version, watch it crash with a real StackOverflowError on a long list, and fix three real bugs. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
A train is a chain of coaches. Every coach is hooked to the next one: coach 1 knows coach 2, coach 2 knows coach 3. Nobody knows the whole train, and the coaches don't need to stand in numbered bays side by side the way array elements sit in memory. The hooks hold the order.
| On the train | In the code |
|---|---|
| A coach | A node object |
| The passengers in a coach | The node's value, val |
| The hook to the next coach | The reference next |
| The engine end (where every walk starts) | head |
| "No coach after me" | next == null |
| Turning the train around at the last station | Reversing the list |
Why would anyone use a linked list instead of an array?
- Adding at the front is O(1). Make the new node point at the old head, then move
head. An array has to shift every element one place right: O(n). - No fixed size, no copying when it grows.
- The price: no index. To reach coach 40 you walk from the engine, coach by coach: O(n).
list[40]in O(1) only works for arrays.
A linked list in Java
public class Main {
static class Node {
int val;
Node next;
Node(int val) { this.val = val; }
}
static Node build(int... a) {
Node head = null;
for (int i = a.length - 1; i >= 0; i--) {
Node n = new Node(a[i]);
n.next = head;
head = n;
}
return head;
}
static String show(Node h) {
StringBuilder sb = new StringBuilder();
for (int k = 0; h != null && k < 12; k++, h = h.next)
sb.append(h.val).append(" -> ");
return sb.append(h == null ? "null" : "...").toString();
}
public static void main(String[] args) {
Node head = build(1, 2, 3, 4, 5);
System.out.println(show(head));
System.out.println("head = " + head.val + ", second = " + head.next.val);
}
}
Output:
1 -> 2 -> 3 -> 4 -> 5 -> null
head = 1, second = 2
static class Nodeis a nested class: one file, oneMain, and still a separateNodetype.nextstarts asnullby default.buildadds each value at the front (n.next = head; head = n;), going from the last value to the first, so the list comes out in the original order. Each add is O(1).showfollowsnextuntilnull. It stops after 12 nodes and prints..., so a broken list with a loop can't print forever (you'll need this in Bug 3).
Problem statement
Given the head of a singly linked list, reverse the list and return the new head.
Input: 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: 5 -> 4 -> 3 -> 2 -> 1 -> null
- The new head is the old last node.
- Change the links, not the values. Real nodes can carry big objects (a passenger record, a song in a playlist) and other code may hold references to them. Move the coaches, not the passengers.
- Edge cases: one node, two nodes, an empty list (
head == null).
Brute force: unhook the last coach
A yard worker's way: walk to the last coach (remembering the one before it), unhook it, attach it to the end of a new train, and repeat until the old train is empty.
static Node bruteReverse(Node head) {
Node newHead = null, tail = null;
while (head != null) {
Node before = null, last = head;
while (last.next != null) {
before = last;
last = last.next;
}
if (before == null) head = null;
else before.next = null;
if (newHead == null) newHead = last;
else tail.next = last;
tail = last;
}
return newHead;
}
show(bruteReverse(build(1, 2, 3, 4, 5))) printed 5 -> 4 -> 3 -> 2 -> 1 -> null. Correct, and it only moves links.
The big input: 2 lakh nodes
Playlists, browser histories and log files can have lakhs of entries. We built a list 1 .. 200000 and timed the brute force:
int n = 200000;
int[] a = new int[n];
for (int i = 0; i < n; i++) a[i] = i + 1;
Node head = build(a);
long t0 = System.nanoTime();
Node r = bruteReverse(head);
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("new head = " + r.val + ", " + ms + " ms");
Result: Time Limit Exceeded (more than 8 seconds; on our machine it was still running after 40 seconds).
Why the brute force is slow
A list can't jump to its end. Every "find the last coach" walks from the head: n hops, then n − 1, then n − 2 ... That adds up to about n² / 2.
| Nodes | Hops (about n²/2) |
|---|---|
| 1,000 | 5 lakh: instant |
| 20,000 | 20 crore |
| 2,00,000 | 2 × 10¹⁰: far past 8 seconds |
"Copy the values into an array and write them back reversed" is O(n) time, but it needs O(n) extra memory and it moves values, not nodes, so interviewers don't accept it.
The key insight: flip every arrow in one walk
The reversed train is the same coaches in the same places, only every arrow points the other way. So walk from the front once and flip each arrow as you pass it.
The danger: the moment you set curr.next = prev, you've lost the only way to reach the rest of the list. So save next before flipping. Three hands:
| Pointer | Meaning |
|---|---|
prev |
the part already reversed (starts as null) |
curr |
the node we're fixing now (starts at head) |
next |
the rest of the list, saved before the flip |
Trace on 1 -> 2 -> 3 -> 4 -> 5:
| Step | Flip | prev after | curr after |
|---|---|---|---|
| start | null | 1 | |
| 1 | 1 → null | 1 | 2 |
| 2 | 2 → 1 | 2 | 3 |
| 3 | 3 → 2 | 3 | 4 |
| 4 | 4 → 3 | 4 | 5 |
| 5 | 5 → 4 | 5 | null: stop, return prev = 5 |
loop while curr != null:
next = curr.next (1) save the rest of the list
curr.next = prev (2) flip the arrow
prev = curr (3) move prev forward
curr = next (4) move curr forward
return prev the old last node = the new head
before step 2: null <- 1 <- 2 3 -> 4 -> 5 -> null (prev = 2, curr = 3, next = 4)
after step 4: null <- 1 <- 2 <- 3 4 -> 5 -> null (prev = 3, curr = 4)
The optimal solution in Java
public class Main {
static class Node {
int val;
Node next;
Node(int val) { this.val = val; }
}
static Node build(int... a) {
Node head = null;
for (int i = a.length - 1; i >= 0; i--) {
Node n = new Node(a[i]);
n.next = head;
head = n;
}
return head;
}
static String show(Node h) {
StringBuilder sb = new StringBuilder();
for (int k = 0; h != null && k < 12; k++, h = h.next)
sb.append(h.val).append(" -> ");
return sb.append(h == null ? "null" : "...").toString();
}
static Node reverse(Node head) {
Node prev = null, curr = head;
while (curr != null) {
Node next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
public static void main(String[] args) {
System.out.println(show(reverse(build(1, 2, 3, 4, 5))));
System.out.println(show(reverse(build(7))));
System.out.println(show(reverse(build(1, 2))));
System.out.println(show(reverse(null)));
}
}
Output:
5 -> 4 -> 3 -> 2 -> 1 -> null
7 -> null
2 -> 1 -> null
null
With an empty list the loop never runs and we return prev, which is null. On the 2 lakh node list, reverse printed new head = 200000, 4 ms.
The recursive solution
Trust recursion with the rest of the list:
- Base case: empty or one node is already reversed.
newHead = reverseRec(head.next)reverses everything afterhead.head.next(node 2) is now the tail of that reversed part.- Hook
headbehind it:head.next.next = head. - Cut
head's forward arrow:head.next = null. - Return
newHeadunchanged all the way up.
static Node reverseRec(Node head) {
if (head == null || head.next == null) return head;
Node newHead = reverseRec(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
On 1..5, 7 and null it printed 5 -> 4 -> 3 -> 2 -> 1 -> null, 7 -> null, null. On the 2 lakh node list it crashed:
Exception in thread "main" java.lang.StackOverflowError
at Main.reverseRec(Main.java:24)
at Main.reverseRec(Main.java:24)
...
Every call waits for the next one, and each waiting call keeps a stack frame. 2 lakh nodes need 2 lakh frames; Java's default call stack holds far fewer. So the recursive version costs O(n) stack space. In an interview, write the loop, and say this sentence.
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int val;
Node* next;
Node(int v) : val(v), next(nullptr) {}
};
Node* build(const vector<int>& a) {
Node* head = nullptr;
for (int i = (int)a.size() - 1; i >= 0; i--) {
Node* n = new Node(a[i]);
n->next = head;
head = n;
}
return head;
}
string show(Node* h) {
string s;
for (; h; h = h->next) s += to_string(h->val) + " -> ";
return s + "null";
}
Node* reverseList(Node* head) { // iterative: O(n) time, O(1) space
Node *prev = nullptr, *curr = head;
while (curr) {
Node* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
Node* reverseRec(Node* head) { // recursive: O(n) time, O(n) stack
if (!head || !head->next) return head;
Node* newHead = reverseRec(head->next);
head->next->next = head;
head->next = nullptr;
return newHead;
}
int main() {
cout << show(reverseList(build({1, 2, 3, 4, 5}))) << "\n";
cout << show(reverseList(build({7}))) << "\n";
cout << show(reverseList(build({}))) << "\n";
cout << show(reverseRec(build({1, 2, 3, 4, 5}))) << "\n";
}
Output:
5 -> 4 -> 3 -> 2 -> 1 -> null
7 -> null
null
5 -> 4 -> 3 -> 2 -> 1 -> null
The same solution in Python
class Node:
def __init__(self, val, next=None):
self.val = val
self.next = next
def build(*a):
head = None
for x in reversed(a):
head = Node(x, head)
return head
def show(h):
out = []
while h:
out.append(str(h.val))
h = h.next
return " -> ".join(out + ["null"])
def reverse_list(head): # iterative: O(n) time, O(1) space
prev, curr = None, head
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
return prev
def reverse_rec(head): # recursive: O(n) stack (Python's limit is about 1000 calls)
if head is None or head.next is None:
return head
new_head = reverse_rec(head.next)
head.next.next = head
head.next = None
return new_head
print(show(reverse_list(build(1, 2, 3, 4, 5))))
print(show(reverse_list(build(7))))
print(show(reverse_list(build())))
print(show(reverse_rec(build(1, 2, 3, 4, 5))))
Output: the same four lines as C++. In Python the recursive version fails much sooner: on 5,000 nodes it raised RecursionError: maximum recursion depth exceeded.
Three real bugs
Bug 1: flipping before saving next
while (curr != null) {
curr.next = prev;
prev = curr;
curr = curr.next;
}
Output: 1 -> null. After the flip, curr.next is already null, so the loop jumps to null and stops. Nodes 2 to 5 are lost: nothing points at them any more. Fix: Node next = curr.next; first.
Bug 2: while (curr.next != null)
On 1..5 it printed 4 -> 3 -> 2 -> 1 -> null (node 5 was never flipped or returned), and on an empty list:
Exception in thread "main" java.lang.NullPointerException: Cannot read field "next" because "<local2>" is null
at Main.reverse(Main.java:24)
at Main.main(Main.java:34)
Fix: loop while curr != null.
Bug 3: recursion without head.next = null
Output: 5 -> 4 -> 3 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> 1 -> 2 -> .... Node 1 still points to 2, and 2 now points back to 1: a cycle. Our show stopped after 12 nodes; a normal printing loop would never end. Detecting cycles is the next episode.
Complexity
| Approach | Time | Extra space | 2 lakh nodes |
|---|---|---|---|
| Unhook the last node, repeat | O(n²) | O(1) | Time Limit Exceeded |
| Copy values into an array, write back | O(n) | O(n) | fast, but moves values |
Iterative prev / curr / next |
O(n) | O(1) | 4 ms |
| Recursive | O(n) | O(n) call stack | StackOverflowError |
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
curr.next = prev; ... curr = curr.next; |
1 -> null |
next wasn't saved before the flip |
Node next = curr.next; first |
while (curr.next != null) |
4 -> 3 -> 2 -> 1 -> null; NullPointerException on null |
the last node is skipped | while (curr != null) |
Recursion without head.next = null |
... 2 -> 1 -> 2 -> 1 -> ... |
1 and 2 point at each other | cut the arrow after hooking |
return head; after the loop |
1 -> null |
the old head is now the tail | return prev; |
Printing the old head after reversing |
1 -> null |
head still points at node 1 |
use the returned head |
| Recursion on a very long list | java.lang.StackOverflowError |
one stack frame per node | use the loop |
Mini project: a browser's "recently visited" list
Keep the pages a user visits as a linked list (newest at the front, added in O(1)). Add a "show oldest first" button that reverses the list in place, prints it, and reverses it back.
Node history = null;
for (int page : new int[]{101, 205, 318, 402}) { // page ids, newest is 402
Node n = new Node(page);
n.next = history;
history = n;
}
System.out.println("newest first: " + show(history));
history = reverse(history);
System.out.println("oldest first: " + show(history));
history = reverse(history);
It printed newest first: 402 -> 318 -> 205 -> 101 -> null and oldest first: 101 -> 205 -> 318 -> 402 -> null. Extension: keep only the last 10 pages (cut the list after 10 nodes).
Practice
- Reverse only positions 2 to 4 of
1 -> 2 -> 3 -> 4 -> 5(1-based), in one pass.
Solution
Walk before to the node just before position left. Then, right - left times, take the node after curr and move it to the front of the section.
static Node reverseBetween(Node head, int left, int right) {
Node dummy = new Node(0);
dummy.next = head;
Node before = dummy;
for (int i = 1; i < left; i++) before = before.next;
Node curr = before.next;
for (int i = 0; i < right - left; i++) {
Node move = curr.next;
curr.next = move.next;
move.next = before.next;
before.next = move;
}
return dummy.next;
}
It printed 1 -> 4 -> 3 -> 2 -> 5 -> null. The dummy node handles left = 1 without a special case. O(n) time, O(1) space.
- Find the middle node in one walk.
Solution
Two pointers: slow moves 1 step, fast moves 2. When fast reaches the end, slow is in the middle.
static Node middle(Node head) {
Node slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
For 1..5 it returned 3; for 1..6 it returned 4 (the second middle).
- Is the list a palindrome, in O(1) extra space?
Solution
Find the middle, reverse the second half, and compare it with the first half.
static boolean isPalindrome(Node head) {
Node second = reverse(middle(head));
for (Node a = head, b = second; b != null; a = a.next, b = b.next)
if (a.val != b.val) return false;
return true;
}
1 2 3 2 1 → true, 1 2 2 1 → true, 1 2 3 → false. (In a real system, reverse the second half back afterwards so the caller's list is unchanged.)
- Print a list backwards without changing it.
Solution
Recursion: print the rest first, then yourself. O(n) stack, so only for short lists.
static void printBackwards(Node h) {
if (h == null) return;
printBackwards(h.next);
System.out.print(h.val + " ");
}
For 1 -> 2 -> 3 it printed 3 2 1.
Quick quiz
Node head = build(1, 2, 3);
Node r = reverse(head);
System.out.println(show(head));
1 -> 2 -> 3 -> null3 -> 2 -> 1 -> null1 -> nullnull
Answer
1 -> null. head still points at node 1, and node 1 is now the tail, so its next is null. Meanwhile show(r) is 3 -> 2 -> 1 -> null. Always use the returned head. (Real output: 1 -> null.)
Interview questions
- Reverse a linked list iteratively. Time and space? Three pointers; O(n) time, O(1) space.
- And recursively? What's the catch? O(n) time but O(n) call-stack space; very long lists overflow the stack (
StackOverflowErrorin Java,RecursionErrorin Python). - Why must
nextbe saved before the flip? Aftercurr.next = prev, nothing points to the rest of the list. - Why not just swap values? The question asks for the links; nodes may hold large data or be referenced elsewhere, and values may be immutable.
- Array vs linked list: when is each better? Array: O(1) index access, cache-friendly. Linked list: O(1) insert/delete at a known position (front, or after a node you hold), no resizing.
- Reverse positions
left..rightonly. Dummy node + "move the next node to the front of the section" loop, one pass. - Check if a list is a palindrome in O(1) space. Middle with slow/fast, reverse the second half, compare.
- What does the reversed list's old head point to?
null: it is the new tail.
Glossary
| Term | Meaning |
|---|---|
| Linked list | A chain of nodes, each holding a value and a reference to the next node |
| Node | One element of a linked list: val + next |
head |
The reference to the first node; the only way into the list |
next |
A node's reference to the following node |
null |
"No object": the last node's next is null |
| Singly linked list | Each node knows only the next node (not the previous one) |
| Static nested class | A class declared inside another with static, like Node inside Main |
| Reference | A variable that points to an object instead of holding it |
| Traversal | Walking the list from head, following next until null |
| Insert at the front | n.next = head; head = n;: O(1) |
prev / curr / next |
The three pointers of the iterative reversal |
| Dummy node | A fake node placed before the head so the first real node needs no special case |
| Recursion | A function that calls itself on a smaller input until a base case |
| Base case | The input small enough to answer directly (empty or one node) |
| Call stack / stack frame | Memory that holds each active function call; one frame per waiting call |
StackOverflowError |
Java's error when the call stack runs out, e.g. too-deep recursion |
NullPointerException |
Java's error when you read a field (like .next) of null |
| Cycle | A node's next points back to an earlier node, so the list never ends |
| O(n) / O(n²) | Linear work / work that grows with the square of the input size |
| Time Limit Exceeded (TLE) | Too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
Summary
- A linked list is nodes hooked by
next, ending innull;headis the only way in. Adding at the front is O(1); reaching position i is O(i). - Brute force (find the last node again and again) is O(n²) and times out on 2 lakh nodes.
- Iterative reversal: save
next, flipcurr.next = prev, moveprevandcurr, returnprev. O(n) time, O(1) space. - Recursive reversal works too, but uses O(n) stack and overflows on long lists.
- Always use the returned head: the old head is now the tail.
Next episode: Floyd's cycle detection and the cycle start.