Stably reorder a linked list in place by priority lane
A help desk keeps its ticket queue as a singly linked list, in the order tickets arrived. Before each shift, the queue is rearranged by priority lane: every urgent ticket first, then normal ones, then low priority. Within a lane, tickets keep their arrival order so nobody gets skipped. Tickets with a lane the desk does not recognize go to the very end.
Implement sortIntoLanes(head, laneOf, lanes). It rearranges the list in place and returns the new head.
sortIntoLanes(head, laneOf, lanes) // => new head node, or null
Every node is a plain object with a value and a next pointer. The last node has next: null. An empty list is null.
laneOf(value) returns the lane of a node’s value. Call it exactly once per node, in list order.lanes is an array of lane names in priority order. Lanes are compared the way a Map compares keys, so they can be strings, numbers or other values.lanes[0] first, then every node of lanes[1], and so on. Nodes whose lane is not in lanes come last.lanes is empty, the order does not change.next pointers: do not create nodes, copy them into an array, or change any value. The last node of the result has next: null.// T1(low) -> T2(urgent) -> T3(normal) -> T4(urgent) -> T5(spam) -> T6(low)
sortIntoLanes(head, (ticket) => ticket.lane, ['urgent', 'normal', 'low']);
// T2 -> T4 -> T3 -> T1 -> T6 -> T5
// 5 -> 12 -> 7 -> 30
sortIntoLanes(head, (n) => (n >= 10 ? 'big' : 'small'), ['big', 'small']);
// 12 -> 30 -> 5 -> 7
sortIntoLanes(null, laneOf, ['urgent']); // => null