1 题目

2 思想

3 代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:        
        if head is None or head.next is None : # 如果就仅有一个节点
            return head
        mid = self.splitList(head)
        left_head = self.sortList(head)
        right_head = self.sortList(mid)
        
        res = self.mergeList(left_head,right_head) 
        return res
        
    # 根据快慢指针将一个链表一分为二
    def splitList(self,head):
        slow = fast = head
        while(fast.next and fast.next.next):
            fast = fast.next.next
            slow = slow.next
        tmp = slow.next
        slow.next = None # 要断开
        # 将链表一份为二
        return tmp


    # 合并两个链表
    # 让这里的输入 head1 与 head2 不可能是None
    def mergeList(self,head1,head2):
        # 判断是否是特殊情况
        if head1 is None and head2 is None: 
            return None        
        
        # 得到头结点
        if head1.val <= head2.val:
            start = head1
            head1 = head1.next
        else:
            start = head2
            head2 = head2.next
        
        # 开始 merge
        tail = start
        while(head1 and head2):
            if head1.val <= head2.val:
                tail.next = head1
                head1 = head1.next
            else:
                tail.next = head2
                head2 = head2.next
            tail = tail.next
        
        if head1:
            tail.next = head1
        if head2:
            tail.next = head2

        # 返回合并后的头节点
        return start