Reverse Linked List
You get the head of a singly linked list. Each node has a value and a pointer to the next node, and the last node points to nothing.
Reverse the list so that every pointer points the other way, and return the head of the reversed list. The list may be empty, in which case you return nothing.
Examples
Input head = [1, 2, 3, 4, 5]
Output [5, 4, 3, 2, 1]
Input head = [1, 2]
Output [2, 1]
Input head = []
Output []
Constraints
- 0 <= number of nodes <= 500
- -5,000 <= node value <= 5,000
Stuck? Take one hint at a time
Common mistakes
- Overwriting current.next before saving the next node, which loses the rest of the list.
- Returning current instead of previous at the end of the loop, which is always nothing.
- Forgetting to set the old head's next to nothing in the recursive version, which leaves a cycle between the first two nodes.
- Allocating new nodes for a reversed copy, which uses O(n) extra memory instead of O(1).
Questions an interviewer may ask next
- Reverse only the nodes between positions left and right. (Reverse Linked List II.)
- Reverse the nodes in groups of k. (Reverse Nodes in k-Group.)
- Check whether a linked list is a palindrome using O(1) extra memory. (Reverse the second half.)
- Reverse a doubly linked list. What changes? (Swap next and prev in every node.)
head
[1,2,3,4,5]
Expected output
[5,4,3,2,1]
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.