Reverse Linked List
easy●Linked Lists
Given the `head` of a singly linked list, reverse the list, and return the reversed list.
### How it works (Iterative approach): To reverse a linked list, we essentially need to change the direction of all the "next" pointers so that each node points to its previous node instead of its next node.
We use three pointers to accomplish this gracefully without losing the rest of the list: 1. `prev`: Initially `null`. This will represent the new "next" node for the current node we are processing. 2. `curr`: Initially `head`. The current node we are operating on. 3. `nextTemp`: Used inside the loop to temporarily store `curr.next` before we overwrite it.
**The Loop:** While `curr` is not null: 1. Save the next node: `nextTemp = curr.next` 2. Reverse the pointer: `curr.next = prev` 3. Advance `prev` to `curr` 4. Advance `curr` to `nextTemp`
At the end of the loop, `curr` will be null, and `prev` will point to the new head of the reversed list!
### How it works (Iterative approach): To reverse a linked list, we essentially need to change the direction of all the "next" pointers so that each node points to its previous node instead of its next node.
We use three pointers to accomplish this gracefully without losing the rest of the list: 1. `prev`: Initially `null`. This will represent the new "next" node for the current node we are processing. 2. `curr`: Initially `head`. The current node we are operating on. 3. `nextTemp`: Used inside the loop to temporarily store `curr.next` before we overwrite it.
**The Loop:** While `curr` is not null: 1. Save the next node: `nextTemp = curr.next` 2. Reverse the pointer: `curr.next = prev` 3. Advance `prev` to `curr` 4. Advance `curr` to `nextTemp`
At the end of the loop, `curr` will be null, and `prev` will point to the new head of the reversed list!
Constraints
- The number of nodes in the list is the range [0, 5000].
- -5000 <= Node.val <= 5000
TimeO(O(n))
SpaceO(O(1))
Ready to startStep 0 / 0
TypeScript