Reverse Linked List

Reverse a singly linked list and return the new head.

A way to picture it

It's a conga line, and everyone has a hand on the shoulder of the person in front. To turn the line around, each dancer lets go and grabs the person behind instead. The catch: before letting go, you have to remember who was in front, or the rest of the line wanders off.

How to approach it

Walk with prev, curr and next. Save next, point curr back at prev, then step both forward. prev ends up as the new head.

Example

Input: {"head":[1,2,3,4,5]}. Output: [5,4,3,2,1].

Complexity: O(n) time and O(1) space. One pass, three pointers, rewired in place.

This page includes an animated walkthrough, Java and Python solutions, and a question to check your understanding.