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

Tracing head = [1,2,3,4,5] (arrows below show the current next pointer of each node — watch them flip one at a time):

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.