题解 | #单链表的排序#

Merge-Sort/合并排序python代码：

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

#
# 
# @param head ListNode类 the head node
# @return ListNode类
#
class Solution:
    def sortInList(self , head ):
        # write code here
        if not head: # 链表为空，返回None
            return None
        if not head.next: # 链表长度为1，递归到底了，直接返回
            return head
        p1,p2=head,head # 分治：p1慢指针，p2快指针
        while p2.next and p2.next.next:
            p1=p1.next
            p2=p2.next.next
        mid=p1.next # 找到链表中点
        p1.next=None # 原链表一分为二，即把左半链表的尾节点p1的next置为None
        q1=self.sortInList(head) # 递归左半链表，传参head是当前头节点，返回左半链表排序好之后的头结点q1
        q2=self.sortInList(mid) # 递归右半链表，传参mid是当前头节点，返回右半链表排序好之后的头结点q2
        h=ListNode(-1) # 合并链表用的辅助节点（在真正的头结点之前），val随便取，比如-1和所有有效节点区分开
        cur=h # 合并链表指针
        while q1 or q2: # 如果左右两个链表中的元素还没有全部遍历完
            if not q1: # 如果左链表为空
                cur.next=q2 # 把右链表指针指向的当前结点放进来
                q2=q2.next # 右链表指针前进1
            elif not q2: # 右链表为空，类似处理
                cur.next=q1
                q1=q1.next
            else: # 如果都不为空
                if q1.val<q2.val: # 两边指针指向的元素比较大小
                    cur.next=q1 # 把小的放进来
                    q1=q1.next # 小的那边指针前进1
                else:
                    cur.next=q2
                    q2=q2.next
            cur=cur.next # 合并链表的指针前进1
        return h.next # 返回合并排序之后的链表头结点，注意是辅助节点的next