Sort a linked list in O(n log n) time using constant space complexity.

Example 1:


Input: 4->2->1->3
Output: 1->2->3->4


Example 2:


Input: -1->5->3->4->0
Output: -1->0->3->4->5

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Sorting

Amortized analysis

Divide and conquer

Starter code: # Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        

Solutions: