SyntaxPilot
Courses/DSA and Coding Problems/Lesson 21
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 21 of 90

Linked lists: reverse a list, iterative and recursive

queued

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 Node is a nested class: one file, one Main, and still a separate Node type. next starts as null by default.
  • build adds 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).
  • show follows next until null. 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:

  1. Base case: empty or one node is already reversed.
  2. newHead = reverseRec(head.next) reverses everything after head. head.next (node 2) is now the tail of that reversed part.
  3. Hook head behind it: head.next.next = head.
  4. Cut head's forward arrow: head.next = null.
  5. Return newHead unchanged 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

  1. 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.

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

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

  1. 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 -> null
  • 3 -> 2 -> 1 -> null
  • 1 -> null
  • null
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

  1. Reverse a linked list iteratively. Time and space? Three pointers; O(n) time, O(1) space.
  2. And recursively? What's the catch? O(n) time but O(n) call-stack space; very long lists overflow the stack (StackOverflowError in Java, RecursionError in Python).
  3. Why must next be saved before the flip? After curr.next = prev, nothing points to the rest of the list.
  4. 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.
  5. 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.
  6. Reverse positions left..right only. Dummy node + "move the next node to the front of the section" loop, one pass.
  7. Check if a list is a palindrome in O(1) space. Middle with slow/fast, reverse the second half, compare.
  8. 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 in null; head is 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, flip curr.next = prev, move prev and curr, return prev. 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.