text: class ListNode:
      def __init__(self, val=0, next=None):
          self.val = val
          self.next = next
  
  class Solution:
      def merge(self, left, right):
          # 归并环节
          dummy_head = ListNode(-1)
          cur = dummy_head
          while left and right:
              if left.val <= right.val:
                  cur.next = left
                  left = left.next
              else:
                  cur.next = right
                  right = right.next
              cur = cur.next
          
          if left:
              cur.next = left
          elif right:
              cur.next = right
              
          return dummy_head.next
          
      def mergeSort(self, head: ListNode):
          # 分割环节
          if not head or not head.next:
              return head
          
          # 快慢指针找到中心链节点
          slow, fast = head, head.next
          while fast and fast.next:
              slow = slow.next 
              fast = fast.next.next 
          
          # 断开左右链节点
          left_head, right_head = head, slow.next 
          slow.next = None
          
          # 归并操作
          return self.merge(self.mergeSort(left_head), self.mergeSort(right_head))
      
      
      def sortLinkedList(self, head: ListNode):
          return self.mergeSort(head)