Prioritize User Segments in Linked List
Clevertap needs to efficiently manage and prioritize user segments for targeted campaigns. User profiles, identified by unique IDs, are sometimes stored in a linked list representing event streams or a temporary processing queue. For a new high-priority campaign, we need to reorder this list to prioritize "premium" users (odd IDs) over "standard" users (even IDs), while ensuring a specific ordering within each segment for optimal engagement.
Implement a function prioritizeUsers that takes the head of a singly linked list of user IDs (positive integers). The function should reorder the list such that:
The relative order of nodes with identical IDs within their respective segments (Premium or Standard) does not matter.
function prioritizeUsers(head: ListNode | null): ListNode | null
head: The head of a singly linked list where each ListNode contains a positive integer val representing a user ID.
returns: The head of the reordered linked list.
ListNode structure:
class ListNode {
val: number
next: ListNode | null
constructor(val?: number, next?: ListNode | null) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
}
head = null) should return null.O(N log N)) and space complexity (O(1) auxiliary space, excluding recursion stack for merge sort which is O(log N)).Examples
Example 1
Input:
head = [3,1,4,2,5]
Output:
[5,3,1,4,2]
Note:
Original list: 3 -> 1 -> 4 -> 2 -> 5
Premium (odd) users: 3, 1, 5. Sorted descending: 5 -> 3 -> 1
Standard (even) users: 4, 2. Sorted descending: 4 -> 2
Combined: 5 -> 3 -> 1 -> 4 -> 2
Example 2
Input:
head = [10,20,5,15]
Output:
[15,5,20,10]
Note:
Original list: 10 -> 20 -> 5 -> 15
Premium (odd) users: 5, 15. Sorted descending: 15 -> 5
Standard (even) users: 10, 20. Sorted descending: 20 -> 10
Combined: 15 -> 5 -> 20 -> 10
Example 3
Input:
head = [1,3,5]
Output:
[5,3,1]
Note:
All users are Premium (odd). The list is sorted in descending order.
Constraints
N is between 0 and 10^5.ListNode.val (user ID) is between 1 and 10^9.ListNode objects for the reordering process; you must re-use the existing nodes by modifying their next pointers.Loading editor...