Reverse a LL
MediumThe same three-pointer flip
Problem
Given the head of a singly linked list, reverse it and return the new head.
Walk the list flipping each node's arrow to point backwards, one link at a time.
The idea
Walk the list redirecting each node's next to the node behind it, keeping a saved reference to the node ahead so the walk can continue. It is the pattern that underlies palindrome checks, k-group reversal and reordering.
The trick
- Three pointers: prev, curr, next.
- The recursive version is elegant but costs O(n) stack.
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.