0206.Reverse Linked List

• Link: 206. Reverse Linked List - Easy
• Track: NeetCode150

Question

Restate the problem

• Given the head of a singly linked list, reverse the list and return the new head.
• We are not creating a different logical list. We are rewiring each node’s next pointer so the direction is flipped.

Edge Case

• empty list: head = None, return None
• single node: return the same node
• while reversing, do not lose the rest of the list, so save cur.next first

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	Iterative (prev / cur)	$O(n)$	$O(1)$
Method 2	Recursive (reverse suffix)	$O(n)$	$O(n)$

Method 1 - Iterative (prev / cur)

Approach

• Keep two pointers:
  • prev: the head of the already-reversed part
  • cur: the node we are currently processing
• For each node:
  1. Save cur.next into nxt
  2. Reverse the pointer: cur.next = prev
  3. Move prev forward to cur
  4. Move cur forward to nxt
• When cur becomes None, prev is the new head.

Why this works

• At any moment:
  • prev points to the reversed prefix
  • cur points to the remaining unreversed suffix
• Each iteration removes one node from the suffix and attaches it to the front of the reversed prefix.

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(1)$

Code

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        prev = None
        
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        
        return prev

Method 2 - Recursive

Approach

• Let recursion reverse the list starting from head.next.
• After the smaller subproblem returns:
  • head.next is the last node of the reversed suffix
  • so connect it back to head with head.next.next = head
• Then cut head.next = None to avoid a cycle.
• Return the new head of the reversed list.

Complexity

• Time Complexity: $O(n)$
• Space Complexity: $O(n)$ because of recursion stack

Code

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

---

Mistake

• Forgetting to save next before doing cur.next = prev
  • If you overwrite cur.next first and do not store the original next node, you lose the rest of the list.
• Forgetting head.next = None in the recursive solution
  • That creates a cycle instead of a properly terminated reversed list.