Frontend School

Prioritize User Segments in Linked List

DSA
hard

Prioritize User Segments in Linked List

Hard
Linked List
Sorting
Algorithms
Data Structures

Overview

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.

What you need to do / Task

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:

  1. All nodes with odd user IDs (Premium users) appear before all nodes with even user IDs (Standard users).
  2. Within the Premium user segment, nodes must be sorted by user ID in descending order.
  3. Within the Standard user segment, nodes must be sorted by user ID in descending order.

The relative order of nodes with identical IDs within their respective segments (Premium or Standard) does not matter.

Input & output

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)
    }
}

Clarifications

  • An empty input list (head = null) should return null.
  • A list with a single node should return the node itself.
  • User IDs are always positive integers.
  • The solution should aim for optimal time complexity (O(N log N)) and space complexity (O(1) auxiliary space, excluding recursion stack for merge sort which is O(log N)).

Examples

1

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

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

3

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

Constraints & assumptions

  • The number of nodes in the list N is between 0 and 10^5.
  • ListNode.val (user ID) is between 1 and 10^9.
  • The list will only contain positive integers.
  • You are not allowed to create new ListNode objects for the reordering process; you must re-use the existing nodes by modifying their next pointers.

What interviewers evaluate

  • Correctness of partitioning logic for odd/even user IDs.
  • Efficient and correct implementation of linked list sorting (e.g., Merge Sort adapted for descending order).
  • Handling of edge cases (empty lists, single-node lists, or lists with only odd/even nodes).
  • Optimal time and space complexity.

Loading editor...