All problems

Latest Song Requests

Medium · linked list

A radio station collects song requests in a singly linked list. Each node holds the number of a song, and the nodes are in the order the requests arrived, oldest first. Listeners often ask for the same song again and again.

The presenter only wants to play each song once, at the moment of its most recent request. So for every song number, keep only its last node in the list and remove all of its earlier nodes. The nodes that remain must stay in their original order.

Return the head of the shortened list. An empty list stays empty. The nodes you receive are ListNode objects with a val and a next; you may re-point them.

Examples

Example 1

Input: head = [3, 1, 3, 2, 1]

Output: [3, 2, 1]

Song 3 was last requested at the third place, song 2 at the fourth and song 1 at the fifth. The first 3 and the first 1 are dropped.

Example 2

Input: head = [5, 5, 5]

Output: [5]

Only the last request for song 5 remains.

Example 3

Input: head = [4, 8, 6]

Output: [4, 8, 6]

Every song was requested once, so nothing is removed.

Constraints