Reverse a LinkedList
MediumFlip each next pointer as you walk
Problem
Given the head of a singly linked list, reverse the list and return the new head.
Walk the list flipping each node's arrow to point backwards, one link at a time.
The idea
Carry three pointers — previous, current and the saved next — and point each node back at its predecessor. Saving next before overwriting it is the entire trick; without it you cannot reach the rest of the list.
The trick
- Save next, redirect current, advance both prev and current. In that order.
- prev ends up as the new head; the old head becomes the tail with a null next.
- O(n) time, O(1) space.
Step 1 of 6. A linked list is boxes joined by arrows. To reverse it we flip every arrow to point backwards — no boxes move.
Three pointers: prev, cur, next.
1let prev = null, cur = head;2while (cur) {3 const next = cur.next;4 cur.next = prev;5 prev = cur;6 cur = next;7}8return prev;Input
- list
- [1, 2, 3, 4]
Memory
- cur
- = 0
- next
- —
- prev
- —
- head
- —
Output
- new head
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- list = 1 -> 2 -> 3 -> 4
- Output:
- 4 -> 3 -> 2 -> 1
- Explanation:
- All the arrows flip direction.
Example 2
- Input:
- list = 1 -> 2
- Output:
- 2 -> 1
- Explanation:
- Two nodes swap ends.
Example 3
- Input:
- list = 7
- Output:
- 7
- Explanation:
- A single node reverses to itself.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.