1. Reverse Linked List

Description

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 - Iteration

• Take 2 Nodes one for previous and one for current and loop an with the use of temp Node change the links
• Time: O(n) Space: O(1)
• We iterate through the n nodes and only use constant space
• Standard way what we need to change we store first then we change it to new value then we just push both nodes one ahead
• Check if recursive solution is really required

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
 
        while (curr != null) {
            ListNode tmp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = tmp;
        }
 
        return prev;
    }
}

Recursive Solution (Unwinding / Call-Stack Approach)

Recursively traverse to the end of the list to find the new head, then flip the links backward as the call stack unwinds.

• Intuition: Think of it in two simple phases:

1. Reach the End: Recurse all the way down until head.next == null. That last node is returned back as the newHead.
2. Flip on the Way Back: For the current node head, its next neighbor is head.next. Point that neighbor back to head (head.next.next = head), and sever head’s old forward link (head.next = null) to avoid cycles.

class Solution {
    public ListNode reverseList(ListNode head) {
        // Base case: empty list or reached the last node
        if (head == null || head.next == null) {
            return head;
        }
        
        // 1. Recurse down to find the new head (the last node)
        ListNode newHead = reverseList(head.next);
        
        // 2. Point the next node back to the current node
        head.next.next = head;
        
        // 3. Sever the old forward link
        head.next = null;
        
        return newHead;
    }
}
 

• Time Complexity: $O(N)$
• Space Complexity: $O(N)$ (due to the recursive call stack)

Brute Force Solution (Using an Auxiliary Array / Stack)

Traverse the list, store all values in a stack (or array), and then traverse the list again to overwrite the values in reverse order.

• Intuition: A Stack works as Last-In, First-Out (LIFO), which naturally reverses elements.

class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null) return null;
        
        Stack<Integer> stack = new Stack<>();
        ListNode curr = head;
        
        // Step 1: Push all values onto the stack
        while (curr != null) {
            stack.push(curr.val);
            curr = curr.next;
        }
        
        // Step 2: Pop values back to reverse the data
        curr = head;
        while (curr != null) {
            curr.val = stack.pop();
            curr = curr.next;
        }
        
        return head;
    }
}
 

• Time Complexity: $O(N)$
• Space Complexity: $O(N)$ (requires extra space for the stack)

---

Optimized Solution (In-Place 3-Pointer Iteration)

Instead of copying values, flip the directional arrows (next pointers) in place using three pointers: prev, curr, and next.

The Intuitive Mental Trick (The 4-Step Loop):
Think of traveling down the list node by node. For every node, you:

1. Save: Save curr.next in a temporary variable so you don’t lose the rest of the list.
2. Flip: Turn curr.next around to point backwards at prev.
3. Move Prev: Shift prev forward to curr.
4. Move Curr: Shift curr forward to your saved node.

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        
        while (curr != null) {
            ListNode nextNode = curr.next; // 1. Save next node
            curr.next = prev;              // 2. Flip arrow back
            prev = curr;                   // 3. Move prev forward
            curr = nextNode;              // 4. Move curr forward
        }
        
        return prev; // prev is the new head of the reversed list
    }
}
 

• Time Complexity: $O(N)$
• Space Complexity: $O(1)$ (constant space)