14  Reverse a Singly Linked List

Rank 12 · Pattern: pointer rewiring with saved next node · Target: \(O(n)\) time, \(O(1)\) space

14.1 Problem definition

Given the head of a singly linked list, reverse the list and return its new head.

14.2 Clarifying questions

  1. Can the input list be empty?
  2. Should I reuse and relink the existing nodes, or create a copied list?
  3. May I modify the input list?
  4. Is the input guaranteed to be an acyclic, properly terminated list?

14.3 Sample answers

  1. Yes. Return null for an empty list.
  2. Reuse every existing node; do not copy data nodes.
  3. Yes. Update the existing next references in place.
  4. Yes. Following next from the head eventually reaches null.

14.4 Special data structure: ListNode

Each language defines the minimum node type because its standard collections do not expose a mutable interview-style singly linked node.

static class ListNode {
    int value;
    ListNode next;
    ListNode(int value) { this.value = value; }
}

References link mutable nodes; null ends the list.

ListNode stores value and mutable next attributes. None ends the list.

Option<Box<ListNode>> represents an owned link. The loop uses take() to detach the next link before moving the existing box into the reversed prefix; no data node is copied.

%%{init: {
  "theme": "base",
  "flowchart": {
    "htmlLabels": false
  },
  "themeVariables": {
    "primaryColor": "#ffffff",
    "secondaryColor": "#ffffff",
    "tertiaryColor": "#ffffff",
    "primaryTextColor": "#222222",
    "primaryBorderColor": "#555555",
    "lineColor": "#555555",
    "edgeLabelBackground": "#ffffff"
  }
}}%%
flowchart TB
  H["head reference"]
  N1["ListNode: value = 1"]
  N2["ListNode: value = 2"]
  N3["ListNode: value = 3"]
  Z["null"]

  H --> N1
  N1 --> N2
  N2 --> N3
  N3 --> Z

  classDef node fill:#ffffff,stroke:#555555,stroke-width:1.5px,color:#222222;
  classDef reference fill:#ffffff,stroke:#555555,stroke-width:1.5px,stroke-dasharray:5 3,color:#222222;
  class N1,N2,N3 node;
  class H,Z reference;

The list-building and value-collection helpers exist only to make tests readable; they are not part of the algorithm.

14.5 Approach and invariant

Maintain previous (already reversed) and current (not yet reversed). On every node:

  1. Save current.next before overwriting it.
  2. Point current.next backward to previous.
  3. Advance both pointers.

%%{init: {
  "theme": "base",
  "flowchart": {
    "htmlLabels": false
  },
  "themeVariables": {
    "primaryColor": "#ffffff",
    "secondaryColor": "#ffffff",
    "tertiaryColor": "#ffffff",
    "primaryTextColor": "#222222",
    "primaryBorderColor": "#555555",
    "lineColor": "#555555",
    "edgeLabelBackground": "#ffffff"
  }
}}%%
flowchart TB
  A["BEFORE: previous points to node 1; node 1.next is null"]
  B["BEFORE: current points to node 2; node 2.next points to node 3"]
  C["Save next = node 3"]
  D["Set node 2.next = node 1"]
  E["Set previous = node 2"]
  F["Set current = node 3"]
  G["AFTER: previous chain is 2 to 1 to null"]
  H["AFTER: current chain is 3 to null"]

  A --> C
  B --> C
  C --> D
  D --> E
  E --> F
  F --> G
  F --> H

  classDef state fill:#ffffff,stroke:#555555,stroke-width:1.5px,stroke-dasharray:5 3,color:#222222;
  classDef action fill:#ffffff,stroke:#555555,stroke-width:1.5px,color:#222222;
  class A,B,G,H state;
  class C,D,E,F action;

Invariant: before each iteration, previous heads a correctly reversed prefix and current heads the untouched suffix. Together they contain every original node exactly once.

14.6 Minimal solution

import java.util.*;
import org.junit.*;
import org.junit.runner.*;
import static org.junit.Assert.*;

public class ReverseLinkedListSolution {
    static class ListNode {
        int value;
        ListNode next;
        ListNode(int value) { this.value = value; }
    }

    static ListNode reverse(ListNode head) {
        ListNode previous = null;
        ListNode current = head;
        while (current != null) {
            ListNode next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        return previous;
    }

    static ListNode list(int... values) {
        ListNode sentinel = new ListNode(0);
        ListNode tail = sentinel;
        for (int value : values) {
            tail.next = new ListNode(value);
            tail = tail.next;
        }
        return sentinel.next;
    }

    static List<Integer> values(ListNode head) {
        List<Integer> result = new ArrayList<>();
        for (; head != null; head = head.next) {
            result.add(head.value);
        }
        return result;
    }

    @Test public void emptyListRemainsEmpty() {
        assertNull(reverse(null));
    }

    @Test public void singleNodeIsReturnedByIdentity() {
        ListNode onlyNode = list(7);
        assertSame(onlyNode, reverse(onlyNode));
        assertEquals(List.of(7), values(onlyNode));
    }

    @Test public void reversesTwoNodesInPlace() {
        ListNode first = new ListNode(1);
        ListNode second = new ListNode(2);
        first.next = second;

        ListNode reversed = reverse(first);

        assertSame(second, reversed);
        assertSame(first, second.next);
        assertNull(first.next);
    }

    @Test public void reversesSeveralNodes() {
        ListNode head = list(1, 2, 3);
        ListNode originalTail = head.next.next;
        ListNode reversed = reverse(head);

        assertSame(originalTail, reversed);
        assertEquals(List.of(3, 2, 1), values(reversed));
    }

    @Test public void reversingTwiceRestoresOriginalList() {
        ListNode originalHead = list(1, 2, 3, 4);

        ListNode restored = reverse(reverse(originalHead));

        assertSame(originalHead, restored);
        assertEquals(List.of(1, 2, 3, 4), values(restored));
    }

    public static void main(String[] args) {
        JUnitCore.main("ReverseLinkedListSolution");
    }
}
import unittest


class ListNode:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node


def reverse(head):
    previous = None
    current = head

    while current is not None:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node

    return previous


def linked_list(*values):
    sentinel = ListNode(0)
    tail = sentinel
    for value in values:
        tail.next = ListNode(value)
        tail = tail.next
    return sentinel.next


def list_values(head):
    values = []
    while head is not None:
        values.append(head.value)
        head = head.next
    return values


class ReverseLinkedListTests(unittest.TestCase):
    def test_empty_list(self):
        self.assertIsNone(reverse(None))

    def test_single_node_is_returned_by_identity(self):
        node = ListNode(7)
        self.assertIs(node, reverse(node))

    def test_reverses_two_nodes_in_place(self):
        first = ListNode(1)
        second = ListNode(2)
        first.next = second

        result = reverse(first)

        self.assertIs(second, result)
        self.assertIs(first, second.next)
        self.assertIsNone(first.next)

    def test_reverses_several_nodes(self):
        head = linked_list(1, 2, 3)
        original_tail = head.next.next
        result = reverse(head)
        self.assertIs(original_tail, result)
        self.assertEqual([3, 2, 1], list_values(result))

    def test_reversing_twice_restores_original_list(self):
        original_head = linked_list(1, 2, 3, 4)
        restored = reverse(reverse(original_head))
        self.assertIs(original_head, restored)
        self.assertEqual([1, 2, 3, 4], list_values(restored))


if __name__ == "__main__":
    unittest.main()
#[derive(Debug)]
pub struct ListNode {
    pub value: i32,
    pub next: Link,
}

pub type Link = Option<Box<ListNode>>;

impl ListNode {
    pub fn new(value: i32) -> Self {
        Self { value, next: None }
    }
}

pub fn reverse(mut head: Link) -> Link {
    let mut previous = None;

    while let Some(mut node) = head {
        head = node.next.take();
        node.next = previous;
        previous = Some(node);
    }

    previous
}

#[cfg(test)]
mod tests {
    use super::*;

    fn list(values: &[i32]) -> Link {
        let mut head = None;
        for &value in values.iter().rev() {
            let mut node = Box::new(ListNode::new(value));
            node.next = head;
            head = Some(node);
        }
        head
    }

    fn values(mut head: &Link) -> Vec<i32> {
        let mut result = Vec::new();
        while let Some(node) = head {
            result.push(node.value);
            head = &node.next;
        }
        result
    }

    #[test]
    fn empty_list() {
        assert!(reverse(None).is_none());
    }

    #[test]
    fn single_node() {
        assert_eq!(vec![7], values(&reverse(list(&[7]))));
    }

    #[test]
    fn reverses_several_nodes() {
        assert_eq!(vec![3, 2, 1], values(&reverse(list(&[1, 2, 3]))));
    }

    #[test]
    fn reversing_twice_restores_original_list() {
        let restored = reverse(reverse(list(&[1, 2, 3, 4])));
        assert_eq!(vec![1, 2, 3, 4], values(&restored));
    }
}

The saved next line is the critical safety step. Without it, overwriting current.next loses the rest of the list.

14.7 High-value tests

Input Expected
null null
7 -> null unchanged single node
1 -> 2 -> 3 3 -> 2 -> 1
two nodes swapped order

Also assert identity if reuse matters: the returned head should be the original tail, not a copy.

14.8 Complexity and correctness

Every node is visited once, giving \(O(n)\) time. Three node references use \(O(1)\) space.

One iteration removes current from the untouched suffix and prepends it to the reversed prefix without losing next. This preserves the invariant. At termination the suffix is empty, so previous contains all nodes in reverse order and is the new head.

14.9 If the interviewer pushes

  • A recursive version is concise but uses \(O(n)\) call-stack space and risks stack overflow.
  • Reverse only positions left..right by keeping a pointer to the node before the segment.
  • Reverse in groups of k by checking that a complete group remains before rewiring.
  • For a doubly linked list, swap each node’s next and previous references.

14.10 TDD interview script

Confirm that null is valid, the input is acyclic, existing nodes must be reused, and mutation is required. Then write this test list:

  1. Empty list
  2. Singleton identity
  3. Two-node pointer rewiring
  4. Several-node order and identity
  5. Reversing twice

Use one red–green–refactor cycle per behavior. For reference-based linked structures, assert both values and identity: a copied list can have the correct values while violating the contract. In Rust, ownership and the absence of node allocation in reverse enforce reuse directly. Inspect only externally visible links after the call, and rerun the complete example after each increment.

From book/src, run:

./java/run.sh ReverseLinkedListSolution
./python/run.sh reverse_linked_list_solution
./rust/run.sh reverse_linked_list_solution

Before changing a link, say the safety rule: “I must save current.next before overwriting it, or I lose the untouched suffix.” Then state which reference owns the reversed prefix and which owns the remaining suffix.

14.10.1 Pseudocode

previous = null
current = head

while current is not null:
    next = current.next
    current.next = previous
    previous = current
    current = next

return previous

Before each iteration, previous heads a correctly reversed prefix and current heads the untouched suffix; together they contain each original node exactly once.

14.10.2 TDD sequence

Step Test code added Production code added or changed
1. Empty structure emptyListRemainsEmpty Initialize previous to null; an empty loop returns it.
2. One reused node singleNodeIsReturnedByIdentity Enter the loop once, point the node to null, and return that exact node as previous.
3. First rewiring reversesTwoNodesInPlace Save next, reverse current.next, and advance both references. Identity and the new tail’s null link expose copies or cycles.
4. Entire chain reversesSeveralNodes Repeat the same pointer transition until the untouched suffix is empty; return the original tail.
5. Structural property reversingTwiceRestoresOriginalList Verify the general rewiring is lossless and involutive. No new production branch should be required.

This progression uses identity assertions as contract tests and a metamorphic test—reversing twice—to check the whole structure without depending on private pointer variables.