Skip to content
LEETFLIX

Reverse Linked List

EasyLinked listRecursion
Solve on LeetCode

Three pointers, one loop, zero allocations. The pointer-juggling rite of passage.

01

Problem

Read the prompt, flip through the examples, then steal the idea.

Given the head of a singly linked list, reverse the list, and return the reversed list.

Constraints

  • —The number of nodes in the list is in the range [0, 5000].
  • —-5000 <= Node.val <= 5000

Follow-up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Examples

Input

head =
[1, 2, 3, 4, 5]

Output

[5, 4, 3, 2, 1]

input

∅12345head ▼

output

∅12345head ▼

02

Solution

2 approaches · Python and Go. Pick a tab — the walkthrough follows.

Optimal▶ Animated

Walk the list once, flipping each arrow to point backwards. O(1) extra space.

Keep prev (head of the reversed part), curr (node being processed) and nxt (a lifeline to the unprocessed part). Save, flip, advance, repeat.

Algorithm

  1. prev = None, curr = head.
  2. While curr: save nxt = curr.next.
  3. Flip: curr.next = prev.
  4. Advance: prev = curr, curr = nxt.
  5. Return prev.
Time
O(n)
Space
O(1)
Solution.py
class Solution:    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:        prev = None        curr = head        while curr:            nxt = curr.next   # lifeline to the rest of the list            curr.next = prev  # flip the arrow            prev = curr       # advance both pointers            curr = nxt        return prev
Watch this run

03

Interactive walkthrough

Playing “Iterative — three pointers”. Edit the input, hit Run, then scrub.

Approach: Iterative — three pointers

Loading animation…