Given the head of a singly linked list, reverse the list. Return the new head.
DSA Animator › DSA Revision › Linked List › Reverse Linked List
Remember: save next, flip the arrow, then step forward. Previous ends up as the new head. The video solves Reverse Linked List (LeetCode 206, Easy) with the Pointer Reversal pattern from the Linked List topic, and you can replay every step in the interactive Reverse Linked List animation.
Given the head of a singly linked list, reverse the list. Return the new head.
For 1, 2, 3, 4, 5, the result is 5, 4, 3, 2, 1.
Pushing every value onto a stack and rebuilding uses O of n extra space. We can just flip the arrows in place.
Keep three pointers: previous, current and next. Save next, then point current back at previous. Move previous and current one step forward, and repeat until current is null.
Previous starts at null, and current at 1. Point 1 back to null, then move on to 2. Point 2 back to 1, then 3 back to 2. Then 4 back to 3, and 5 back to 4. Current is null, so previous, at 5, is the new head.
In code, start with previous as null and current as head. In the loop, save next, set current dot next to previous, then shift both pointers. Return previous, so it's O of n time and O of 1 space.
Remember: save next, flip the arrow, then step forward. Previous ends up as the new head.