Reverse a Linked List

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

Example

Text

Input:  1 -> 2 -> 3 -> 4 -> 5
Output: 5 -> 4 -> 3 -> 2 -> 1

graph LR
    subgraph before["before"]
        a1["1"] --> a2["2"] --> a3["3"] --> a4["4"] --> a5["5"] --> an(["null"])
    end
    subgraph after["after"]
        b5["5"] --> b4["4"] --> b3["3"] --> b2["2"] --> b1["1"] --> bn(["null"])
    end

Brute force: build a new list

Walk the original list from front to back and push each value onto the front of a new list. The first value read ends up last, and the last value read ends up first.

A list node here is an object with a mutable next field, and null marks the end of the list. An empty list is null, so no wrapper type is needed.

Java

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode reverseList(ListNode head) {
        ListNode reversed = null;
        for (ListNode cur = head; cur != null; cur = cur.next) {
            reversed = new ListNode(cur.val, reversed);
        }
        return reversed;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(reverseList(fromArray(1, 2, 3, 4, 5))));
    }
}

Output

[5, 4, 3, 2, 1]

Time: O(n). Space: O(n), because it allocates a complete second list. The original becomes garbage once nothing refers to it.

Recursive solution

Carry the reversed-so-far list as a parameter. Each call detaches the first node of head, points it at reversed, and recurses on the rest with that node as the new front of the reversed part.

Java

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode reverseOnto(ListNode head, ListNode reversed) {
        if (head == null) return reversed;
        ListNode rest = head.next;
        head.next = reversed;
        return reverseOnto(rest, head);
    }

    static ListNode reverseList(ListNode head) {
        return reverseOnto(head, null);
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(reverseList(fromArray(1, 2, 3, 4, 5))));
    }
}

Output

[5, 4, 3, 2, 1]

Time: O(n). Space: O(n) for the call stack. Java does not perform tail-call optimization, so this recursion uses one frame per node. A very long list throws StackOverflowError.

Optimal: move the nodes in place

Reuse the existing nodes and change only their next pointers. Keep two lists:

prev: the part that's already reversed (starts empty)
head: the part that isn't reversed yet (starts as the whole list)

Each step moves the first node of head to the front of prev.

Walkthrough with 1 -> 2 -> 3:

step	node taken	`head` after	`prev` after
start		1 → 2 → 3	null
1	1	2 → 3	1
2	2	3	2 → 1
3	3	null	3 → 2 → 1

Java

public class Main {
    static class ListNode {
        int val;
        ListNode next;

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode node = head;
            head = node.next; // 1. remember the rest of the list
            node.next = prev; // 2. point this node at the reversed part
            prev = node;      // 3. this node is the new front of the reversed part
        }
        return prev;
    }

    static ListNode fromArray(int... values) {
        ListNode head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            head = new ListNode(values[i], head);
        }
        return head;
    }

    static String show(ListNode list) {
        StringBuilder sb = new StringBuilder("[");
        for (ListNode n = list; n != null; n = n.next) {
            if (n != list) sb.append(", ");
            sb.append(n.val);
        }
        return sb.append("]").toString();
    }

    public static void main(String[] args) {
        System.out.println(show(reverseList(fromArray(1, 2, 3, 4, 5))));
        System.out.println(show(reverseList(fromArray(7))));
        System.out.println(show(reverseList(null)));
    }
}

Output

[5, 4, 3, 2, 1]
[7]
[]

Time: O(n). Space: O(1).

The order of the three steps matters. Step 2 overwrites node.next, so step 1 must save the old value first. Step 3 must come after step 2, or prev would change before node is linked to it. After the loop, the original head object is the last node of the reversed list and its next is null, so no cycle is left behind. This loop is the base for many other problems: reversing a sublist, reversing in groups of k, swapping pairs, and checking whether a list is a palindrome.

Edge cases

Empty list: the loop doesn't run, and null is returned.
One node: the node is moved to prev and returned unchanged.