题解 | 单链表的排序

——核心思路：使用分治的思想进行求解，先将链表分成一个个最小的单个节点（单个节点就一定有序），然后再进行合并成一个个有序的子链表

对链表进行排序，使用分治的思路，将链表拆分为一个个节点，然后进行合并，

示例：

分 1,3,2,4,5 --> 1 3 2 4 5

合 1,3 2,4 5 --> 1,3 2,4,5 --> 1,2,3,4,5

# 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: ListNode) -> ListNode:
        # 对链表进行排序，使用分治的思路，将链表拆分为一个个节点，然后进行合并，
        #  分 1,3,2,4,5 --> 1   3   2   4   5
        #  合 1,3    2,4     5 --> 1,3   2,4,5   --> 1,2,3,4,5

        if head == None or head.next == None:
            return head

        # 使用快慢指针找中间位置进行切分
        slow = head
        mind = head.next
        fast = head.next.next
        while fast != None and fast.next != None:
            slow = slow.next
            mind = slow.next
            fast = fast.next.next

        # 将慢指针的next指针置为空，拆分成两个子链
        slow.next = None

        # 递归调用进行切分
        return self.merge(self.sortInList(head), self.sortInList(mind))

    # 这个合并方法中的两个链表都是有序的，将两个有序链表进行合并然后return
    def merge(self, left: ListNode, right: ListNode) -> ListNode:
        if left == None:
            return right
        if right == None:
            return left

        dummy = ListNode(-1)  # 定义一个链表的头节点
        p = dummy
        # 两个链表都不为空，判断每个链表头节点哪个val值较小
        while left != None and right != None:
            if left.val <= right.val:
                tmp = left
                left = left.next
                p.next = tmp
                p = p.next
            else:
                tmp = right
                right = right.next
                p.next = tmp
                p = p.next

        # right还有剩余
        if left == None:
            p.next = right
        if right == None:
            p.next = left

        return dummy.next