Rearrange Linked List Descending | Dataford Interview Questions

A Flipkart product-feed service stores item priorities in a singly linked list. Rearrange the list so that node values appear in descending order and return the new head.

Modify the existing links in place. Do not create a separate array of values or new list nodes. The relative order of nodes with equal values should be preserved.

Formal Specification

Implement sort_linked_list_descending(head), where head is either None or a ListNode with integer field value and pointer field next. Return the head of the same linked list after sorting. The judge serializes the returned list as an array of values.

Constraints

0 <= n <= 10^5
-10^9 <= node.value <= 10^9
The input is a singly linked list
No new ListNode objects may be created
The solution must run in O(n log n) time

Function Signature

def sort_linked_list_descending(head):

Your question is Rearrange Linked List Descending. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem