本文共 1257 字，大约阅读时间需要 4 分钟。

题目

基本思路

归并排序（应用快慢指针将链表一分为二）

实现代码

# Definition for singly-linked list.# class ListNode(object):#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution(object):    def sortList(self, head):        """        :type head: ListNode        :rtype: ListNode        """        # 归并排序        if head == None or head.next == None:            return head        fast = slow = head        while fast.next and fast.next.next:            slow = slow.next            fast = fast.next.next        head1,head2 = head,slow.next        slow.next = None        head1 = self.sortList(head1)        head2 = self.sortList(head2)        head = self.mergeList(head1,head2)        return head    def mergeList(self,head1,head2):        if head1 == None:            return head2        if head2 == None:            return head1        p = dummy = ListNode(0)        while head1 and head2:            if head1.val > head2.val:                p.next = head2                head2 = head2.next                p = p.next            else:                p.next = head1                head1 = head1.next                p = p.next        if head1 == None:            p.next = head2        if head2 == None:            p.next = head1        return dummy.next