Algorithms / Linked List Reversal
Least You Need to Know: Reversing a Linked List with Prev, Current, and Next
Linked-list reversal is the interview archetype for pointer discipline: keep track of what was before, what you are on, and what comes next. The core invariant is that one prefix has already been reversed while the remaining suffix is still untouched.
جو کم از کم جاننا ضروری ہے
- Iterative reversal commonly uses three pointers: `prev`, `current`, and `next_node`.
- At each step, save the next node before reversing the current pointer.
- The new head after a full reversal is the old tail, which ends up in `prev`.
- Loop invariants help: one part is reversed, the rest is unreversed.
- Partial reversals need careful tracking of the nodes just before and after the reversed window.
اہم علامتیں
prev
head of the already reversed prefix
current
node currently being processed
next_node
saved successor before redirecting current.next
مختصر حل شدہ مثال
- Start with `prev = null`, `current = head`.
- Save `next_node = current.next`.
- Set `current.next = prev`, then move `prev = current` and `current = next_node`.
- When `current` becomes null, `prev` is the new head of the reversed list.
عام غلطیاں
- Students sometimes move `current` before saving the old next pointer.
- Students sometimes forget that the original head becomes the new tail and should point to null in a full reversal.
- Partial reversals require reconnecting both sides of the reversed segment.
اس قسم کے سوال کو کیسے پہچانیں
- The task asks to reverse a whole list or a contiguous part of it.
- A prev/current/next picture makes the intended invariant obvious.
- Only pointer changes are needed; no array copy is necessary.
Next recommended lesson
Continue through this topic with Least You Need to Know: Merging Sorted Lists and Splicing Runs.
Least You Need to Know: Merging Sorted Lists and Splicing RunsRelated lessons
Keep going with nearby lessons in the same topic.