💬 Discord
Sign In
NeetCode #303LC-206EasyLinked ListBlind 75NC 150NC 250
← Back to All Problems

#303 · #206 · Reverse Linked List(反转链表)

📌 Problem Statement & Constraints

Given the head of a singly linked list, reverse the list and return the new head. Constraints: the number of nodes is in [0, 5000], -5000 <= Node.val <= 5000. The follow-up asks for both an iterative and a recursive solution.

💡 Core Algorithmic Approaches

  1. Walk the list while maintaining prev (the already-reversed prefix) and cur (the remaining list).
  2. At each step, save cur.next, point cur.next at prev, then advance prev = cur and cur = saved.
  3. When cur becomes None, prev is the new head.
  4. Python's simultaneous tuple assignment expresses the three-pointer update in one line, which is both concise and safe.

💻 Benchmark Python3 Implementation

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


# Recursive variant: reverse the tail, then attach the head at the end
class Solution2:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head                # base case
        new_head = self.reverseList(head.next)
        head.next.next = head          # the old tail now points back at head
        head.next = None               # head becomes the new tail
        return new_head

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(1) for the iterative version; O(n) for the recursion stack.

⚠️ Interview Pitfalls & Follow-ups

  • Losing the rest of the list: cur.next must be saved before it is overwritten. The tuple assignment does this implicitly.
  • Returning head: after the loop, head is the old head, which is now the tail. Return prev.
  • Forgetting head.next = None in the recursion: the new tail would still point at the reversed list, creating a cycle.
  • Using recursion on a long list: Python's default recursion limit is about 1000, so a 5000-node list would overflow.