Reverse Linked List — Stack Overflow at 5,000 Nodes

package io.thecodeforge.list;

/**
 * Generic singly linked list node.
 * Used as the building block for all reversal examples.
 */
public class LinkedListNode {

    int value;                  // The data this node holds
    LinkedListNode next;        // Pointer to the next node in the chain (null if tail)

    // Constructor — creates a node with no successor yet
    public LinkedListNode(int value) {
        this.value = value;
        this.next = null;       // Every node starts as a standalone island
    }

    // ─── Helper: build a linked list from an array of integers ───────────────
    public static LinkedListNode buildList(int[] values) {
        if (values == null || values.length == 0) return null;

        LinkedListNode head = new LinkedListNode(values[0]); // First node becomes head
        LinkedListNode current = head;

        for (int i = 1; i < values.length; i++) {
            current.next = new LinkedListNode(values[i]); // Chain each new node
            current = current.next;                       // Advance the pointer
        }
        return head;
    }

    // ─── Helper: print the list so we can verify results ────────────────────
    public static void printList(LinkedListNode head) {
        LinkedListNode current = head;
        StringBuilder output = new StringBuilder();

        while (current != null) {
            output.append(current.value);
            if (current.next != null) output.append(" → "); // Arrow between nodes
            current = current.next;
        }
        output.append(" → null");
        System.out.println(output);
    }
}

package io.thecodeforge.list;

/**
 * Iterative in-place linked list reversal.
 * Production-safe: O(n) time, O(1) space, no stack depth risk.
 */
public class IterativeReversal {

    /**
     * Reverses a singly linked list in-place using three pointers.
     * Time:  O(n) — visits every node exactly once
     * Space: O(1) — only three pointer variables, no extra data structures
     *
     * @param  head  The current head of the list
     * @return       The new head (old tail) after reversal
     */
    public static LinkedListNode reverseIterative(LinkedListNode head) {

        LinkedListNode previousNode = null;    // Starts as null — new tail points to null
        LinkedListNode currentNode  = head;    // Start walking from the head

        while (currentNode != null) {          // Keep going until we fall off the end

            // STEP 1: Save next BEFORE we destroy the forward link
            LinkedListNode nextNode = currentNode.next;

            // STEP 2: Reverse the pointer — current now points BACKWARD
            currentNode.next = previousNode;

            // STEP 3: Slide the 'previous' window forward
            previousNode = currentNode;

            // STEP 4: Slide the 'current' window forward using our saved reference
            currentNode = nextNode;
        }

        // When the loop ends, currentNode is null and previousNode is the new head
        return previousNode;
    }

    // ─── Demo ──────────────────────────────────────────────────────────────────
    public static void main(String[] args) {

        // Build: 1 → 2 → 3 → 4 → 5 → null
        LinkedListNode head = LinkedListNode.buildList(new int[]{1, 2, 3, 4, 5});

        System.out.print("Before reversal: ");
        LinkedListNode.printList(head);        // Show the original list

        LinkedListNode newHead = reverseIterative(head);

        System.out.print("After  reversal: ");
        LinkedListNode.printList(newHead);     // Show the reversed list

        // Edge case: single element list
        LinkedListNode singleNode = new LinkedListNode(42);
        LinkedListNode reversedSingle = reverseIterative(singleNode);
        System.out.print("Single node:     ");
        LinkedListNode.printList(reversedSingle);

        // Edge case: null (empty list)
        LinkedListNode reversedNull = reverseIterative(null);
        System.out.println("Null list:       " + reversedNull); // Should print null
    }
}

package io.thecodeforge.list;

/**
 * Recursive linked list reversal.
 * Elegant but carries O(n) stack depth — use only on bounded input.
 */
public class RecursiveReversal {

    private static final int MAX_SAFE_DEPTH = 5000;

    /**
     * Reverses a singly linked list using recursion.
     * Time:  O(n) — every node is visited once across all stack frames
     * Space: O(n) — one stack frame per node (WATCH OUT on large lists)
     *
     * @param  head  The current head of the list (or sublist in recursive calls)
     * @return       The new head of the fully reversed list
     */
    public static LinkedListNode reverseRecursive(LinkedListNode head) {
        return reverseRecursive(head, 0);
    }

    /**
     * Overloaded version with depth guard for production safety.
     */
    private static LinkedListNode reverseRecursive(LinkedListNode head, int depth) {

        // Depth guard: fail fast instead of letting the JVM crash
        if (depth > MAX_SAFE_DEPTH) {
            throw new IllegalStateException(
                "Recursion depth exceeded " + MAX_SAFE_DEPTH + ". " +
                "Use iterative reversal for large lists.");
        }

        // BASE CASE: empty list or single node — nothing to reverse, return as-is
        if (head == null || head.next == null) {
            return head; // This node becomes the new head of the reversed list
        }

        // RECURSIVE STEP: trust that everything from head.next onward gets reversed
        // newHead will be the last node of the original list (our eventual new head)
        LinkedListNode newHead = reverseRecursive(head.next, depth + 1);

        // At this point, head.next still points to the node just after head.
        // That node is now the TAIL of the reversed sublist.
        // We need it to point back at head to complete the reversal.
        head.next.next = head;  // Ex: if head=1 and head.next=2, make 2 → 1

        // head is now the tail of the fully reversed list, so it must point to null
        head.next = null;

        // Bubble the new head all the way back up the call stack
        return newHead;
    }

    // ─── Demo ──────────────────────────────────────────────────────────────────
    public static void main(String[] args) {

        // Build: 10 → 20 → 30 → 40 → null
        LinkedListNode head = LinkedListNode.buildList(new int[]{10, 20, 30, 40});

        System.out.print("Before reversal: ");
        LinkedListNode.printList(head);

        LinkedListNode newHead = reverseRecursive(head);

        System.out.print("After  reversal: ");
        LinkedListNode.printList(newHead);

        // Verify edge cases
        System.out.println("Null input:      " + reverseRecursive(null));

        LinkedListNode solo = new LinkedListNode(99);
        System.out.print("Single node:     ");
        LinkedListNode.printList(reverseRecursive(solo));
    }
}

package io.thecodeforge.list;

/**
 * Reverses a sublist between positions left and right (1-indexed).
 * Surrounding nodes remain untouched.
 */
public class SublistReversal {

    /**
     * Reverses only the nodes between positions 'left' and 'right' (1-indexed).
     * Everything outside that range stays untouched.
     *
     * Example: list=1→2→3→4→5, left=2, right=4  →  1→4→3→2→5
     *
     * Time:  O(n)
     * Space: O(1)
     */
    public static LinkedListNode reverseSublist(
            LinkedListNode head, int left, int right) {

        if (head == null || left == right) return head; // Nothing to reverse

        // Dummy node before the real head — simplifies edge cases where left=1
        LinkedListNode dummy = new LinkedListNode(0);
        dummy.next = head;

        // Walk to the node just BEFORE the reversal window
        LinkedListNode beforeLeft = dummy;
        for (int step = 1; step < left; step++) {
            beforeLeft = beforeLeft.next; // Move (left-1) steps from dummy
        }

        // 'sublistHead' is the first node entering the reversal zone
        // After reversal it will become the TAIL of the reversed segment
        LinkedListNode sublistHead = beforeLeft.next;

        // Run the standard three-pointer reversal for (right - left) iterations
        LinkedListNode previousNode = null;
        LinkedListNode currentNode  = sublistHead;

        for (int step = 0; step <= right - left; step++) {
            LinkedListNode nextNode = currentNode.next; // Save next before overwriting
            currentNode.next = previousNode;            // Reverse the pointer
            previousNode = currentNode;                 // Slide previous forward
            currentNode = nextNode;                     // Slide current forward
        }

        // At this point:
        //   previousNode → new front of the reversed segment (old 'right' node)
        //   currentNode  → first node AFTER the reversed segment (right+1 node)
        //   sublistHead  → tail of the reversed segment (old 'left' node)

        // Reconnect: node before window → new front of reversed segment
        beforeLeft.next = previousNode;

        // Reconnect: old front (now tail) → first node after the window
        sublistHead.next = currentNode;

        return dummy.next; // Return real head (may have changed if left=1)
    }

    // ─── Demo ──────────────────────────────────────────────────────────────────
    public static void main(String[] args) {

        // Test 1: reverse middle segment
        LinkedListNode list1 = LinkedListNode.buildList(new int[]{1, 2, 3, 4, 5});
        System.out.print("Original:          ");
        LinkedListNode.printList(list1);
        LinkedListNode result1 = reverseSublist(list1, 2, 4);
        System.out.print("Reversed [2..4]:   ");
        LinkedListNode.printList(result1);

        // Test 2: reverse from the very start
        LinkedListNode list2 = LinkedListNode.buildList(new int[]{1, 2, 3, 4, 5});
        LinkedListNode result2 = reverseSublist(list2, 1, 3);
        System.out.print("Reversed [1..3]:   ");
        LinkedListNode.printList(result2);

        // Test 3: reverse entire list
        LinkedListNode list3 = LinkedListNode.buildList(new int[]{1, 2, 3, 4, 5});
        LinkedListNode result3 = reverseSublist(list3, 1, 5);
        System.out.print("Reversed [1..5]:   ");
        LinkedListNode.printList(result3);
    }
}