1033. Reverse a Two-Way Chain
A playlist app stores songs in a doubly linked list where each node knows its prev and next neighbour. A user taps the 'play backwards' button. Given head, the first node of the list, reverse the order of the list so the old last song becomes the first, and make sure both prev and next links of every node match the new order.
Return the new head, or null if the list is empty. Reverse in place: do not create new nodes. The solution should run in O(n) time and O(1) extra space.
Example 1
- Input:
- head = [1,2,3,4]
- Output:
- [4,3,2,1]
- Explanation:
The order is reversed so the old tail 4 becomes the new head: 4, 3, 2, 1.
Example 2
- Input:
- head = [5,5,9]
- Output:
- [9,5,5]
- Explanation:
Equal values do not matter; positions are reversed to give 9, 5, 5.
Constraints
0 ≤ list length n ≤ 105
-104 ≤ node value ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n)
- Space
- O(1)