Reverse a singly linked list

Question

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

1 -> 2 -> 3 -> 4 -> None
becomes
4 -> 3 -> 2 -> 1 -> None

Reverse the list iteratively in $O(n)$ time and $O(1)$ extra space. Copying values into a Python list and rebuilding is not accepted, the point is pointer surgery.

Accepted Answer

Walk the list once, and at each node flip its next pointer to point backwards. You need to save the forward pointer before overwriting it, so the loop carries three references: the already-reversed prefix (prev), the current node, and the untouched suffix (nxt). After the loop, curr is None and prev is the old tail, the new head. Tracing 1 - 2 - 3: after step one the state is None <- 1 with 2 - 3 remaining; after step two, None <- 1 <- 2 with 3 remaining; after step three, 3 - 2 - 1. Time O(n), space O(1). The recursive version is elegant but uses O(n) stack and will blow Python's recursion l…

Reverse a singly linked list

Your answer

More Coding questions