JuniorCodeVery commonNot answered yet
Reverse a singly-linked list
Given the head of a singly-linked list of Node, reverse the list in-place and return the new head.
Requirements:
- O(n) time, O(1) extra space (iterate; do not copy values into an array).
- Handle the empty list and a single-element list.
struct Node {
int val;
Node* next;
};
Node* reverseList(Node* head) {
// your code here
}Write the implementation.
Use three pointers: prev (initially nullptr), curr, and next. Iterate: save next, point curr->next to prev, advance prev to curr, advance curr to saved next. When curr is null, prev is the new head. Time O(n), space O(1).
- ✗Losing the next node before overwriting curr->next — always save
next = curr->nextfirst - ✗Returning curr instead of prev at the end — curr is null when the loop exits
- ✗Not handling empty list or single-element list edge cases
- →How would you reverse a doubly-linked list?
- →How would you reverse only a sub-range [m, n] of a linked list?
Contents
Task
Given a singly-linked list structure, write a function that reverses the list in-place and returns the new head.
Solution
struct Node { int val; Node* next; };
// Iterative — O(n) time, O(1) space
Node* reverseList(Node* head) {
Node* prev = nullptr;
Node* curr = head;
while (curr) {
Node* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}Key points
- Always save
nextbefore overwritingcurr->next. - When the loop exits,
curris null andprevis the new head. - Prefer iterative over recursive to avoid O(n) stack depth.
Contents
