Reverse Linked List

Read every value into a list, then build a brand new linked list in the opposite order. Simple to reason about, but it allocates an entirely new set of nodes instead of reusing the ones you already have.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        values = []
        node = head
        while node:
            values.append(node.val)
            node = node.next

        dummy = ListNode()
        tail = dummy
        for v in reversed(values):
            tail.next = ListNode(v)
            tail = tail.next
        return dummy.next

Correct, and O(n) time, but the extra O(n) space for the new nodes is unnecessary — every node we need already exists, we just need to point them the other way.

Walk the list once, and at each node flip its next pointer to point backward to the node you came from instead of forward. You need to save curr.next in a temporary variable first, since you’re about to overwrite it and would otherwise lose the rest of the list.

class Solution:
    def reverseList(self, head: ListNode | None) -> ListNode | None:
        prev = None
        curr = head
        while curr:
            next_node = curr.next   # save before overwriting
            curr.next = prev        # reverse the pointer
            prev = curr             # advance prev
            curr = next_node        # advance curr
        return prev

Watch the three pointers: prev is where a link flips back to, curr is the node being rewired, and next_node preserves the escape route the instant before curr.next is overwritten.

Why it’s correct: every node’s next pointer is redirected exactly once, to the node that preceded it in the original list — after n iterations, every link has been flipped and prev sits on the old tail, which is now the new head. Complexity: single pass, three pointer variables → O(n) time, O(1) space — this is optimal, since producing a reversed list requires touching every node at least once.