题解 | #单链表的排序#

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param head ListNode类 the head node
# @return ListNode类
#
class Solution:
        def recur_cut(self, head: ListNode, tail: ListNode) -> ListNode:
            if head == tail:
                return head

            fast, slow = head, head
            while fast.next.next is not None:
                fast = fast.next.next
                slow = slow.next
                if fast.next is None:
                    break

            rhead = slow.next
            slow.next = None
            left_link = self.recur_cut(head, slow)
            right_link = self.recur_cut(rhead, tail)

            left_p, right_p = left_link, right_link
            merge_head = None
            merge_p = None
            while left_p is not None and right_p is not None:
                if left_p.val <= right_p.val:
                    if merge_p is None:
                        merge_p = left_p
                        merge_head = merge_p
                    else:
                        merge_p.next = left_p
                        merge_p = left_p
                    left_p = left_p.next
                else:
                    if merge_p is None:
                        merge_p = right_p
                        merge_head = merge_p
                    else:
                        merge_p.next = right_p
                        merge_p = right_p
                    right_p = right_p.next
            if left_p is not None:
                merge_p.next = left_p
            if right_p is not None:
                merge_p.next = right_p
            return merge_head



        def sortInList(self , head: ListNode) -> ListNode:
            # write code here
            if head is None or head.next is None:
                return head

            tail = head
            while tail.next is not None:
                tail = tail.next

            return self.recur_cut(head, tail)

归并排序的思路，先递归拆解链表，直到只有一个节点时结束递归，然后再对左右两个有序链表进行合并。