Reverse a Singly Linked List, thesarfo

Given the head of a singly linked list, reverse the list and return the new head. Input 1 → 2 → 3 → 4 → 5 becomes 5 → 4 → 3 → 2 → 1. (LeetCode 206)

Brute force — use a stack: a stack is LIFO. By pushing values from the list into the stack and popping them out, we get the values in reverse order, then we just overwrite each node’s value with the reversed ones. This reverses the data, not the links.

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode current = head;
        Stack<Integer> stack = new Stack<>();

        // Step 1: Push values into stack
        while (current != null) {
            stack.push(current.val);
            current = current.next;
        }

        current = head;

        // Step 2: Overwrite node values in reverse
        while (current != null) {
            current.val = stack.pop();
            current = current.next;
        }

        return head;
    }
}

Time: O(n) — traverse twice. Space: O(n) — all values live in the stack.

Optimal — reverse in place: instead of reversing the values, reverse the links (the next pointers), done while traversing so it only uses constant space. Three pointers: cur (the node we’re on), prev (the node before cur, starts null), and front (a temp holding cur.next before we overwrite it). When cur becomes null, prev points to the new head.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode front = cur.next; // Save next node
            cur.next = prev;           // Reverse current node's pointer
            prev = cur;                // Move prev forward
            cur = front;               // Move cur forward
        }

        return prev; // New head of the reversed list
    }
}

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