Here is solutions for Reverse Linked List.

1. Understand the Problem

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

Example:

1 → 2 → 3 → 4 → 5 → NULL
Output: 5 → 4 → 3 → 2 → 1 → NULL

2. Clarify Constraints (Ask 4–5 Questions)

1. Can the list be empty? → Yes, return None.

2. Is modifying the original list allowed? → Yes.

3. Only singly linked list, no extra pointers (prev) available? → Yes.

4. Time and space constraints?

   • ⏱ Time: O(n)

   • 💾 Space: O(1) extra (in-place preferred)

5. Do I need to handle very large lists?

→ Yes, iterative preferred to avoid recursion depth issues.

3. Explore examples

4. Brainstorm 2-3 solutions

4.1. Solution 1 – Naive (Recursive) - Time O(N), Space O(N)

• Recursively reverse rest of list and reattach head.

• ❌ Uses O(n) stack → not optimal.

• Time: O(N).

• Space: O(N).

4.2. Solution 2 – Optimized (Iterative) - Time O(N), Space O(1)

• Use three pointers: prev, cur, next.

• Reverse links while traversing.

• Time: O(N).

• Space: O(1).

5. Implement solutions

5.1. Recursion - Time O(N), Space O(N)

• Idea:

  • Use newHead to store the address of the last node of reverse head.

  • Each node when recursive return the address of the head in reverse order.

  • Each node has a fixed address - limit to create new address block.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None

        newHead = head
        if head.next:
            newHead = self.reverseList(head.next)
            head.next.next = head
        head.next = None

        return newHead

• Explain:

reverseList(1)
  reverseList(2)
    reverseList(3)
      reverseList(4)
        returns 4 (base case)

At node 3:

newHead = 4
head = 3
head.next = 4
head.next.next = 3  # 4.next = 3
head.next = None    # 3.next = None

• Time: O(N).

• Space: O(N) for recursion stack.

5.2. Use 3 pointer: prev, curr, next - Time: O(N), Space: O(1)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev, curr = None, head

        while curr:
            temp = curr.next
            curr.next = prev
            prev = curr
            curr = temp
        return prev

• Time: O(N).

• Space: O(1).

6. Dry run examples

• Reverse: [1 -> 2 -> 3 -> 4 -> 5]