【题目描述】

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def sortList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None or head.next is None:return head
        mid=self.getmid(head)
        l=head
        r=mid.next
        mid.next=None
        return self.merge(self.sortList(l),self.sortList(r))
    def getmid(self,head):#链表快慢指针找中点
        slow=fast=head
        if head is None :return slow
        while fast.next and fast.next.next:
            slow=slow.next
            fast=fast.next.next
        return slow
    def merge(self,l,r):
        a=ListNode(0)
        q=a
        while l and r:
            if l.val>r.val:
                q.next=r
                r=r.next
            else:
                q.next=l
                l=l.next
            q=q.next
        if l:
            q.next=l
        if r:
            q.next=r
        return a.next
复制代码