Reverse Linked List
A music app stores each playlist as a singly linked list: every node holds a track number and points to the track that plays after it. For a new play in reverse button, the app needs the same nodes linked in the opposite direction.
Given the head of the playlist, reverse the links so the last track comes first, and return the new head. An empty playlist (head is null) stays empty.
Input: head = [8,3,6,1] Output: [1,6,3,8]
Explanation: Track 1 used to be last, so it becomes the new head.
Input: head = [5,5,2] Output: [2,5,5]
Explanation: Repeated track numbers are separate nodes; only the links change.
Input: head = [12] Output: [12]
Explanation: A one-track playlist reads the same in both directions.
Constraints
- The playlist has between 0 and 5000 nodes.
- Every node value is an integer from -5000 to 5000.
💡 Hint 1
Walk the list once, flipping each next pointer to point backwards.
💡 Hint 2
You need three references: previous, current and the saved next node.
Try it yourself first ✎
Solutions stick better after a real attempt. Peek when you're ready.
Approach
Iterate with prev = null and curr = head. Save curr.next, point curr.next back at prev, then advance both. When curr falls off the end, prev is the new head. (A recursive version works too but uses O(n) stack.)
function reverseList(head) {
let prev = null;
let curr = head;
while (curr) {
const next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null, curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}No submissions yet. Press Submit to run your code against every test.
/**
* Definition for singly-linked list (provided):
* function ListNode(val, next) { this.val = val ?? 0; this.next = next ?? null; }
*
* @param {ListNode} head
* @return {ListNode}
*/
function reverseList(head) {
}Run your code to see results here.