Problem 21 · Linked Lists

Reverse Linked List

EasyClassic DSA & systems

01Problem

Given the head of a singly linked list, reverse the list in place and return the new head.

02Key insight

Walk the list once, re-pointing each node's next to the previous node; three pointers (prev, curr, next) are all the state you need.

03Solution

solution.pypython15 lines

from __future__ import annotations
from dataclasses import dataclass
from typing import Optional

@dataclass
class ListNode:
    val: int
    next: Optional[ListNode] = None

def reverse_list(head: Optional[ListNode]) -> Optional[ListNode]:
    prev: Optional[ListNode] = None
    curr = head
    while curr:
        curr.next, prev, curr = prev, curr, curr.next
    return prev

Try it first.

TimeO(n)

SpaceO(1)

tests.py · 3 passing

tests.pypython13 lines

def build(vals):
    head = None
    for v in reversed(vals):
        head = ListNode(v, head)
    return head
def to_list(node):
    out = []
    while node:
        out.append(node.val); node = node.next
    return out
assert to_list(reverse_list(build([1, 2, 3, 4]))) == [4, 3, 2, 1]
assert reverse_list(None) is None
assert to_list(reverse_list(build([7]))) == [7]

04Staff-level follow-up

Reverse in groups of k? Reverse each k-block with the same loop and stitch the block tail to the next reversed block; leave a short final block untouched.