Reverse the Playlist

Easypointer reversalAlso known as Reverse Linked List

A music app stores each playlist as a chain of songs. Every song only knows which song comes next. There is no list of positions and no way to jump back.

A listener taps "Play in reverse". The app must flip the chain in place, so the last song becomes the first and every song points to the one that used to come before it.

Your task

Write reversePlaylist(head). head is the first node of a singly linked list (each node has val and next). Reverse the list and return the new first node.

An empty playlist is null (None in Python). Lists are shown as arrays like [3, 8, 1, 9] for readability; your function receives and returns real nodes.

reversePlaylist(head: ListNode) → ListNode

Examples

Example 1

Input

head = [3, 8, 1, 9]

Output

[9, 1, 8, 3]

Why

The chain was 3 → 8 → 1 → 9. After flipping every arrow it is 9 → 1 → 8 → 3, and the new head is 9.

Example 2

Input

head = []

Output

[]

Why

An empty playlist stays empty. Return null (None in Python).

Constraints

0 ≤ number of songs ≤ 5,000
Song ids are integers.
Reverse the links; do not just create a reversed copy of the values (though that also passes the tests, it misses the point).

Start with brute force

Walk the list, copy every value into an array, then build a brand-new list from the array backwards.

That is O(n) time, so speed is fine. The cost is O(n) extra memory for the array and the new nodes, and you never practise the real skill: rewiring pointers without losing your place. The in-place version uses O(1) extra memory.

Hints

0 of 4 shown

Hint 1
Look at one node in the middle, say 8 in 3 → 8 → 1 → 9. After reversing, where should its next point?
Hint 2
Every node's next must point to the node that came before it. But a node does not know what came before it. So as you walk forward, you must carry that information yourself.
Hint 3
Keep a variable prev (starting at null) for the node you just visited. When you change current.next, you lose your only way forward. What must you save first?
Hint 4
Walk with three variables: prev, current, and next. Each step: save next = current.next, point current.next = prev, then move prev = current and current = next. When current is null, prev is the new head.

Walkthrough and solution

Unlocks when you pass every test. Stuck for a while? Looking is fine too, as long as you then close it and write the code yourself.

How to solve it

The difficulty is that flipping current.next destroys your only link to the rest of the list. So you save it first.

Trace 3 → 8 → 1:

prev = null, current = 3. Save next = 8. Point 3 → null. Now prev = 3, current = 8.
Save next = 1. Point 8 → 3. Now prev = 8, current = 1.
Save next = null. Point 1 → 8. Now prev = 1, current = null.

The loop stops. The list reads 1 → 8 → 3 → null, and prev holds its head. The empty list works too: the loop never runs and you return null.

Reference solution

function reversePlaylist(head) {
  let prev = null;
  let current = head;
  while (current !== null) {
    const next = current.next; // save the way forward
    current.next = prev;       // flip the arrow
    prev = current;            // step forward
    current = next;
  }
  return prev;
}

def reverse_playlist(head):
    prev = None
    current = head
    while current is not None:
        nxt = current.next   # save the way forward
        current.next = prev  # flip the arrow
        prev = current       # step forward
        current = nxt
    return prev

TimeO(n)Each node is visited once.

SpaceO(1)Three pointer variables, no matter how long the list is.

Learn the idea: Linked Lists

Ctrl+Enter runs

Run your code to see results here. Run checks the examples. Submit checks every test, including hidden edge cases.

Write code