FastPrepSort a Linked List in Descending Order

Sort a Linked List in Descending Order

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW
Learn

Problem statement

Given the head of a singly linked list, sort all of its nodes in nonincreasing order and return the head of the sorted list.

Preserve every node value, including duplicates. The input list may be empty.

Function

sortListDescending(head: ListNode) → ListNode

Examples

Example 1

head = [4,2,1,3]return = [4,3,2,1]

The four nodes are reordered from largest value to smallest value.

Example 2

head = [-1,5,3,4,0]return = [5,4,3,0,-1]

Positive, zero, and negative values are all ordered in descending numeric order.

Example 3

head = []return = []

An empty list is already sorted.

Constraints

  • The list contains at most 50000 nodes.
  • Every node value is a signed 32-bit integer.

More Microsoft problems

See Microsoft hiring insights
/** Definition for singly-linked list.
 * class ListNode { int val; ListNode next; }
 */
public ListNode sortListDescending(ListNode head) {
    // Write your code here.
}
head[4,2,1,3]
expected[4,3,2,1]
Checking account…