Your question is Merge Sort Linked List. Start with the requirements on the right.
Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.
Merck maintains singly linked lists of laboratory sample records ordered by arrival time. Implement merge sort to reorder a linked list by each node's integer value field in ascending order.
The sort must operate by relinking existing nodes rather than copying values into an array. Equal values must remain in their original relative order, so the algorithm should be stable.
The function receives head, either the first ListNode in a singly linked list or None, and returns the head of the sorted list. Each node has the fields value and next:
class ListNode:
def __init__(self, value=0, next=None):
self.value = value
self.next = next
The test cases represent linked lists as arrays of values. The evaluator converts each array into a linked list before calling the function and converts the returned list back into an array.
def sort_list(head):