How do you reverse a singly linked list, iteratively and recursively?

The 30 second answer

Iteratively, I walk the list with two pointers, prev and curr. At each node I save next, point curr back at prev, then move both forward; at the end prev is the new head. That's O(n) time and O(1) extra space. Recursively, I reverse the rest of the list first, then make the next node point back to the current one and clear the current node's next. That's O(n) stack space, so very long lists can overflow.

Iterative. Keep three references: prev (the already-reversed part), curr (the node being flipped) and next (saved before the flip, so the rest of the list is not lost). Each step flips exactly one pointer. When curr becomes null, prev is the old tail and the new head.

Recursive. Assume the call on head.next returns the reversed rest of the list. After it returns, head.next is the last node of that reversed part, so head.next.next = head hangs head on the end, and head.next = null makes it the new tail. The base case is an empty list or a single node.

public class LinkedLists {
    static final class Node {
        int val; Node next;
        Node(int val, Node next) { this.val = val; this.next = next; }
    }

    // Iterative: O(n) time, O(1) extra space.
    static Node reverse(Node head) {
        Node prev = null, curr = head;
        while (curr != null) {
            Node next = curr.next;   // save the rest of the list
            curr.next = prev;        // flip one pointer
            prev = curr;             // move both pointers one step
            curr = next;
        }
        return prev;                 // the old tail is the new head
    }

    // Recursive: O(n) time, O(n) call-stack space.
    static Node reverseRecursive(Node head) {
        if (head == null || head.next == null) return head;
        Node newHead = reverseRecursive(head.next);
        head.next.next = head;       // the node after head now points back to head
        head.next = null;            // head becomes the tail of the reversed part
        return newHead;
    }

    static Node of(int... vals) { Node h = null; for (int i = vals.length - 1; i >= 0; i--) h = new Node(vals[i], h); return h; }
    static String str(Node h) { StringBuilder sb = new StringBuilder("["); for (; h != null; h = h.next) sb.append(h.val).append(h.next != null ? "," : ""); return sb.append("]").toString(); }

    public static void main(String[] args) {
        System.out.println(str(reverse(of(1, 2, 3, 4, 5))));           // [5,4,3,2,1]
        System.out.println(str(reverseRecursive(of(1, 2, 3, 4, 5))));  // [5,4,3,2,1]
        System.out.println(str(reverse(of())) + str(reverse(of(7))));  // [][7]
    }
}

Edge cases to say out loud. An empty list and a single node return unchanged. Interviewers often ask which version you would ship: the iterative one, because the recursive one uses one stack frame per node and a long enough list throws StackOverflowError.

Follow-up: reverse only positions m to n. Walk to the node before position m, reverse the next n − m + 1 nodes with the same three-pointer loop, then reconnect both ends. A dummy node in front of the head removes the special case when m is 1.

Sources (1)

LeetCode 206: Reverse Linked Listleetcode.com