Reverse Linked List
In-place iterative reversal using prev/curr/next bookkeeping — the foundational linked-list primitive.
2 min read
linked-list
Problem#
Reverse a singly linked list and return the new head.
Examples#
[1,2,3,4,5]→[5,4,3,2,1]
Constraints#
- Length in
[0, 5000].
Approach#
Three pointers: prev starts null, curr walks the list, nxt saves the next pointer before rewriting. Each iteration flips curr->next to point at prev, then shifts the trio forward.
Solution#
class Solution {public: ListNode* reverseList(ListNode* head) { ListNode *prev = nullptr, *curr = head; while (curr) { ListNode* nxt = curr->next; curr->next = prev; prev = curr; curr = nxt; } return prev; }};func reverseList(head *ListNode) *ListNode { var prev *ListNode curr := head for curr != nil { nxt := curr.Next curr.Next = prev prev = curr curr = nxt } return prev}from typing import Optional
class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: prev: Optional[ListNode] = None curr = head while curr: nxt = curr.next curr.next = prev prev = curr curr = nxt return prevfunction reverseList(head) { let prev = null, curr = head; while (curr) { const nxt = curr.next; curr.next = prev; prev = curr; curr = nxt; } return prev;}class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null, curr = head; while (curr != null) { ListNode nxt = curr.next; curr.next = prev; prev = curr; curr = nxt; } return prev; }}function reverseList(head: ListNode | null): ListNode | null { let prev: ListNode | null = null; let curr: ListNode | null = head; while (curr !== null) { const nxt: ListNode | null = curr.next; curr.next = prev; prev = curr; curr = nxt; } return prev;}Editorial#
The mnemonic order is save next → rewrite next → advance prev → advance curr. Reverse the four lines and you’ll either lose the rest of the list or never advance. Each node is touched once.
Complexity#
- Time: O(n).
- Space: O(1).
Concept revision#
Related#