LeetCode 206 - Reverse Linked List

This Easy problem reverses a singly linked list and returns its new head. I reused the existing nodes and rewired their next pointers in place, tracking the previous, current, and original next nodes during each iteration.

---

Problem link and explanation

• Problem: 206. Reverse Linked List
• Summary: Given the head of a singly linked list, reverse every next link and return the head of the resulting list.

For example, 1 → 2 → 3 → None must become 3 → 2 → 1 → None. Assigning a node’s next pointer removes its original route to the rest of the list, so that original next node has to be saved before the link changes.

---

Approach

prev points to the head of the portion already reversed, while current is the node being processed. The reversed portion is initially empty, so prev starts as None.

prev = None
current = head

Each iteration saves current.next, points the current node back to prev, and then advances both traversal references.

next_node = current.next
current.next = prev
prev = current
current = next_node

The first node eventually points to None and becomes the tail of the reversed list. When current reaches None, every link has been processed and prev points to the original tail, which is now the new head.

---

Complexity analysis

• Time complexity: O(n)
  • The loop visits every node exactly once.
• Space complexity: O(1)
  • The algorithm uses three references and rewires the existing nodes without allocating a collection that grows with the input.

---

Implementation code

from typing import Optional

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        current = head

        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

        return prev

---

Summary and reflection

The operation depends on one ordering rule: save the original next node before overwriting the current link. Reversing those two statements would lose access to the unprocessed suffix. The loop invariant also keeps the return value clear: prev is always the head of the reversed prefix, so after current moves past the list, prev is the new head.