Merge Sort Linked List

MediumPython

Problem

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.

Formal Specification

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.

Constraints

0 <= n <= 10^5
-10^9 <= node.value <= 10^9
The input list is singly linked
The returned list must reuse the original nodes
Do not convert the list to an array or call built-in sorting

Function Signature

def sort_list(head):

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.

Formal Specification

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.