力扣148 https://leetcode-cn.com/problems/sort-list/
归并排序单向链表 完整解法

# from utils import ListNode, LinkList
from typing import List 
class ListNode(object):
    def __init__(self, val=None, next=None):
        self.val = val 
        self.next = next
    def __repr__(self):
        res = ''
        p = self.next
        res = '' + str(self.val) + '-->'
        while p:
            tmp = str(p.val)
            tmp = tmp + '-->' if p.next else tmp
            res += tmp
            p = p.next
        return res

def LinkList(lst: List) -> ListNode:
    if not lst: return None
    head = ListNode(lst[0])
    p = head 
    for i in range(1, len(lst)):
        p.next = ListNode(lst[i])
        p = p.next 
    return head

def sortList(head: ListNode) -> ListNode:
    if not head or not head.next: return head 
    slow, fast = head, head.next 
    # find the mid and cut the LinkList
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next 
    mid, slow.next = slow.next, None 
    left, right = sortList(head), sortList(mid)
    # merge two sorted LinkList
    dummy = ListNode(0)
    p = dummy
    while left and right:
        if left.val < right.val:
            p.next, left = left, left.next 
        else:
            p.next, right = right, right.next 
        p = p.next
    p.next = left if left else right 
    return dummy.next


if __name__ == "__main__":
    ins = LinkList([1, 6, 3, 9, 7, 5])
    print(ins)
    outs = sortList(ins)
    print(outs)