Reverse Linked List

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

Example 1:

Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

Example 2:

Input: head = [1,2] Output: [2,1]

Example 3:

Input: head = [] Output: []

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Approach: Iterative Reversal with Three Pointers (Optimal Solution)

Algorithm

1. Initialize three pointers: prev = null, curr = head, next = null
2. Iterate through the list
3. Save the next node before changing the current node’s pointer
4. Point curr.next backward to prev
5. Move prev and curr forward one step
6. When curr reaches null, prev is the new head

Key Insight

Reversing requires careful pointer management: before breaking the forward link of curr.next, we must save it in next. Otherwise the rest of the list is lost.

Time & Space Complexity

• Time Complexity: O(n) - single pass through the list
• Space Complexity: O(1) - constant extra space used

Java Implementation

public class ReverseLinkedList {

    /**
     * Definition for singly-linked list.
     */
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /**
     * Iteratively reverse a singly linked list.
     * @param head Head of the linked list
     * @return Head of the reversed list
     */
    public static ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next; // save the next node
            curr.next = prev;          // reverse the link
            prev = curr;               // move prev forward
            curr = next;               // move curr forward
        }

        return prev;
    }

    // Helper method to build a list from an array
    public static ListNode buildList(int[] values) {
        if (values.length == 0) {
            return null;
        }
        ListNode head = new ListNode(values[0]);
        ListNode curr = head;
        for (int i = 1; i < values.length; i++) {
            curr.next = new ListNode(values[i]);
            curr = curr.next;
        }
        return head;
    }

    // Helper method to print a list
    public static void printList(ListNode head) {
        System.out.print("[");
        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) {
                System.out.print(", ");
            }
            curr = curr.next;
        }
        System.out.println("]");
    }

    // Test method
    public static void main(String[] args) {
        // Test case 1
        ListNode head1 = buildList(new int[]{1, 2, 3, 4, 5});
        System.out.print("Input: ");
        printList(head1);
        System.out.print("Output: ");
        printList(reverseList(head1)); // Expected: [5, 4, 3, 2, 1]

        // Test case 2
        ListNode head2 = buildList(new int[]{1, 2});
        System.out.print("Input: ");
        printList(head2);
        System.out.print("Output: ");
        printList(reverseList(head2)); // Expected: [2, 1]

        // Test case 3
        ListNode head3 = buildList(new int[]{});
        System.out.print("Input: ");
        printList(head3);
        System.out.print("Output: ");
        printList(reverseList(head3)); // Expected: []
    }
}

Recursive Approach

public static ListNode reverseListRecursive(ListNode head) {
    // Base case: empty list or single node
    if (head == null || head.next == null) {
        return head;
    }

    // Reverse the rest of the list
    ListNode newHead = reverseListRecursive(head.next);

    // Make the next node point back to the current node
    head.next.next = head;
    head.next = null;

    return newHead;
}

The recursive version assumes the sublist starting at head.next has been reversed and returns its new head, then rewires the links.

Example Walkthrough

For head = [1,2,3,4,5]:

1. prev=null, curr=1: next=2, 1.next=null, prev=1, curr=2
2. prev=1, curr=2: next=3, 2.next=1, prev=2, curr=3
3. prev=2, curr=3: next=4, 3.next=2, prev=3, curr=4
4. prev=3, curr=4: next=5, 4.next=3, prev=4, curr=5
5. prev=4, curr=5: next=null, 5.next=4, prev=5, curr=null

Loop ends, return prev = head of [5,4,3,2,1].

Key Insights

1. Three Pointers: prev, curr, and next manage the link reversal safely
2. Save Before Rewire: The next node must be saved before reassigning curr.next
3. Two Implementations: Both iterative and recursive solutions satisfy the follow-up
4. Empty List: Correctly returns null for an empty input list

The iterative three-pointer approach is the optimal solution, providing linear time complexity with constant space.