A music app stores a playlist as a singly linked list of song IDs, where head is the first song. Write a function that reverses the playlist in place and returns the new head. The list may be empty (head is None / null).
A ListNode class with val and next is provided. In the examples and tests, lists are written as arrays: [1, 2, 3] means 1 → 2 → 3.
text
1reverse_playlist([1, 2, 3, 4]) -> [4, 3, 2, 1]
2reverse_playlist([7]) -> [7]
3reverse_playlist([]) -> []
Example 11 / 2
head
1
2
3
4
null
Before: 1 → 2 → 3 → 4.
Write reverse_playlist(head) in Python or reversePlaylist(head) in JavaScript. Examples are written in Python: in JavaScript, None is null and True / False are true / false.
Runs privately in your browser. Nothing is sent to a server.Ctrl/⌘ + Enter to run · Esc then Tab to leave the editor
Write your function, then run it against 16 tests.
Breakdown
Stuck? Reveal one step at a time, and try again after each one.
What changes?
Reversing doesn't move any values: every arrow just points the other way. In 1 → 2 → 3, node 2's next should become node 1, and node 1's next should become nothing.
Step 2
Walk the list with a "previous" pointer
Keep prev (the part already reversed, starting as nothing) and current (the node you're working on, starting at the head).
Step 3
Rewire one node at a time, in the right order
For each node: save current.next (the rest of the list), point current.next at prev, then move prev up to current, and current on to the saved node.
Step by step1 / 5
prevcurr
null
1
2
3
4
null
prev is null and curr is the head.
Step 4
What do you return?
When current runs off the end, prev is the last node of the original list, which is the new head. Returning the old head is a classic bug: it's now the tail.
Solution
Give it a real try first: you learn far more from a wrong attempt than from reading the answer.
Iterate with prev = None and current = head. Each step saves current.next, reverses the pointer, and advances both. Return prev.
python
1def reverse_playlist(head):
2 prev, current = None, head
3 while current:
4 rest = current.next # save the rest of the list
↑save the rest BEFORE rewiring
5 current.next = prev # point this node backwards
↑point this node backwards
6 prev, current = current, rest
↑move both one step along
7 return prev
↑prev is the new head
javascript
1function reversePlaylist(head) {
2 let prev = null
3 let current = head
4 while (current) {
5 const rest = current.next // save the rest of the list
↑save the rest BEFORE rewiring
6 current.next = prev // point this node backwards
↑point this node backwards
7 prev = current
↑move both one step along
8 current = rest
9 }
10 return prev
↑prev is the new head
11}
Complexity
TimeO(n)SpaceO(1)
O(n) time, one pass over the nodes. O(1) extra space, just three pointers.
What we learned
Save the next node before you overwrite a pointer.
Return the new head (prev), not the old one.
A recursive reversal works too, but uses O(n) call-stack space. Mention the trade-off.