题目链接：https://leetcode.cn/problems/sort-list/
难度：中等

描述：
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

提示：
节点数目：[0, 50000]

题解

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
  8.         def merge_tow_list(l1, l2):
  9.             dummy = ListNode()
  10.             cur = dummy
  11.             while l1 and l2:
  12.                 if l1.val < l2.val:
  13.                     cur.next = l1
  14.                     cur = cur.next
  15.                     l1 = l1.next
  16.                 else:
  17.                     cur.next = l2
  18.                     cur = cur.next
  19.                     l2 = l2.next
  21.             cur.next = l1 if l1 else l2
  22.             return dummy.next
  24.         def merge_sort(head):
  25.             if head is None or head.next is None:
  26.                 return head
  28.             slow, fast = head, head.next
  29.             while fast and fast.next:
  30.                 slow = slow.next
  31.                 fast = fast.next.next
  33.             right_head = slow.next
  34.             slow.next = None
  36.             left = merge_sort(head)
  37.             right = merge_sort(right_head)    
  38.             return merge_tow_list(left, right)
  40.         return merge_sort(head)