Reverse Linked List
Reverse Linked List is an easy Linked List problem from the Blind 75. The key pattern is pointer reversal, and a good solution runs in O(n) time.
Problem
Reverse the singly linked list represented by an array from head to tail and return its new order.
Examples
Example 1
Input
[3,8,1]Output
[1,8,3]Example 2
Input
[1,2]Output
[2,1]Example 3
Input
[9]Output
[9]Approach
Walk the list once, pointing each node back at the previous one while you remember the next node.
| Pattern | Pointer reversal |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
Return the old tail, which is the new head; an empty list stays empty.