【题目描述】
【源代码】 归并排序# 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
复制代码