148. 排序链表(Medium)

题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

样例

Input: [4,2,1,3]
Output: [1,2,3,4]

题解

归并算法 = 有序链表合并 + 分治 + 快慢指针找中点

Python示例

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        def mergeTwoList(l1, l2): # 有序链表合并
            if not l1: return l2 
            if not l2: return l1 
            dummpyHead = ListNode(None)
            p = dummpyHead
            while l1 and l2:
                if l1.val < l2.val:
                    p.next = l1
                    l1 = l1.next 
                else:
                    p.next = l2 
                    l2 = l2.next 
                p = p.next 
            p.next = l1 if l1 else l2 
            return dummpyHead.next

        if not head or not head.next: return head 
        
        # 找中点
        slow, fast = head, head.next 
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next 
        mid = slow.next 
        slow.next = None 

        # 分治
        left, right = self.sortList(head), self.sortList(mid)

        return mergeTwoList(left, right)