Classic Puzzles: Reverse, Middle, Loop

Reverse the arrows

Walk through the list and turn each arrow around. Keep three references: prev, cur and next (so you don't lose the rest of the chain):

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

public class Main {
    static Node build(int... values) {
        Node head = null;
        for (int i = values.length - 1; i >= 0; i--) {
            Node n = new Node(values[i]);
            n.next = head;
            head = n;
        }
        return head;
    }

    static void print(Node head) {
        StringBuilder sb = new StringBuilder();
        for (Node c = head; c != null; c = c.next) sb.append(c.value).append(' ');
        System.out.println(sb.toString().trim());
    }

    static Node reverse(Node head) {
        Node prev = null, cur = head;
        while (cur != null) {
            Node next = cur.next;   // remember the rest
            cur.next = prev;        // turn the arrow around
            prev = cur;             // step forward
            cur = next;
        }
        return prev;                // the old tail is the new head
    }

    static Node middle(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;          // 1 step
            fast = fast.next.next;     // 2 steps
        }
        return slow;
    }

    public static void main(String[] args) {
        Node list = build(1, 2, 3, 4, 5);
        System.out.println("middle: " + middle(list).value);
        list = reverse(list);
        print(list);
    }
}

Output

middle: 3
5 4 3 2 1

Slow and fast pointers

The middle method uses two runners: one moves 1 step, the other 2. When the fast one reaches the end, the slow one is halfway. The same trick finds a loop: if a list loops back on itself, the fast runner eventually laps the slow one and they meet.

Think of it like this: Two runners on a circular track: the faster one always catches the slower one from behind. On a straight road, the fast one just reaches the end.

Remember: Reverse: prev / cur / next. Middle and loops: slow and fast. Both O(n) time and O(1) extra memory.