Reverse Linked List — InterviewPrepKit

Solving tips

The core discipline: save the pointer you're about to overwrite (nxt = curr.next) before flipping curr.next = prev.
Walk with three pointers prev/curr/nxt; when curr becomes None, prev is the new head, so return prev (not curr).
For the recursive version, remember head.next.next = head then head.next = None, and return the unchanged new head from the base case.
Target O(n) time, O(1) space iteratively; recursion is O(n) stack and risks the recursion limit near 5000 nodes.

Problem

Given the head of a singly linked list, reverse the direction of every next pointer so the list reads back-to-front, and return the new head (the node that used to be the tail).

Examples

Input: 1 -> 2 -> 3 -> 4 -> 5 → Output: 5 -> 4 -> 3 -> 2 -> 1 Every link now points the other way; the old tail 5 is the new head.
Input: 1 -> 2 → Output: 2 -> 1 Smallest non-trivial case.
Input: (empty) → Output: (empty) Reversing nothing is nothing.

Constraints

Number of nodes is in [0, 5000].
-5000 <= Node.val <= 5000
Follow-up: solve it both iteratively and recursively.

Think about it first

Hint 1

You can't just walk the list and flip each next pointer naively — the moment you redirect node.next, you lose your only route to the rest of the list. What do you need to save first?

Hint 2

Keep two travelers: prev (the already-reversed part) and curr (the not-yet-reversed part). Each step, point curr.next back at prev — after stashing the old curr.next so you can keep walking.

Hint 3

Recursively: reverse everything after the head first, which returns the new head. Then head.next is the tail of that reversed sublist — hook head on behind it with head.next.next = head and null out head.next.

TL;DR

Iterative three-pointer reversal — O(n) time, O(1) space (recursion is the classic O(n)-stack alternative).

Approach 1 — Brute force: copy values, rebuild backwards

Walk the list once collecting values, then build a brand-new list from the values in reverse.

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

from typing import Optional


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        vals = []
        node = head
        while node:
            vals.append(node.val)
            node = node.next
        new_head = None
        for v in vals:
            new_head = ListNode(v, new_head)
        return new_head

Complexity: O(n) time, O(n) space.

The constraints don’t kill it — the point of the exercise does: the interviewer wants the pointers of the existing nodes rewired in O(1) extra space, not a value copy.

Approach 2 — Iterative pointer reversal

The insight: maintain an invariant with two pointers — prev heads the fully-reversed prefix, curr heads the untouched suffix. One step of work extends the invariant: save curr.next, flip curr.next to point at prev, slide both pointers forward. When curr runs off the end, prev is the new head.

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

from typing import Optional


class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None
        curr = head
        while curr:
            nxt = curr.next   # save the rest of the list
            curr.next = prev  # flip the link
            prev = curr       # advance the reversed prefix
            curr = nxt        # advance into the suffix
        return prev

Walkthrough on 1 -> 2 -> 3 -> 4 -> 5:

step	reversed part (prev)	remaining part (curr)
start	∅	1 -> 2 -> 3 -> 4 -> 5
1	1	2 -> 3 -> 4 -> 5
2	2 -> 1	3 -> 4 -> 5
3	3 -> 2 -> 1	4 -> 5
4	4 -> 3 -> 2 -> 1	5
5	5 -> 4 -> 3 -> 2 -> 1	∅ → return prev

Complexity: O(n) time, O(1) space.

Approach 3 — Recursive reversal

The insight: trust the recursion to reverse the sublist after head and hand back its new head. At that point head.next still points at what is now the tail of the reversed sublist — so head.next.next = head appends head behind it, and head.next = None marks it as the new tail.

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

from typing import Optional


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

Walkthrough on 1 -> 2 -> 3: recursion dives to node 3 (base case, returned as new_head). Unwinding at node 2: 2.next is 3, so 3.next = 2 and 2.next = None, giving 3 -> 2. Unwinding at node 1: 1.next is 2 (now the tail), so 2.next = 1, 1.next = None, giving 3 -> 2 -> 1. new_head = 3 is passed up unchanged.

Complexity: O(n) time, O(n) space for the call stack. At the constraint’s 5000 nodes this brushes against Python’s default recursion limit of 1000 — a real reason to prefer the iterative form.

Common pitfalls

Flipping curr.next before saving it — the rest of the list becomes unreachable and the loop ends after one node.
Returning curr (which is None when the loop exits) instead of prev.
In the recursive version, forgetting head.next = None: the old head keeps a forward link and the list ends in a 2-cycle.
Assuming a non-empty list: both versions must return None untouched for an empty input (the base/loop conditions above already do).

Pattern takeaway

In-place linked-list surgery is always the same discipline: save the pointer you’re about to overwrite, then rewire. The prev/curr/nxt three-pointer walk is the atom of list manipulation — reversal here, and later the inner step of “reverse in k-groups”, “reorder list”, and palindrome checks.