排序链表

难度: Medium

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

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 10⁴] 内
-10⁵ <= Node.val <= 10⁵

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

Submission

运行时间: 520 ms

内存: 29.9 MB

# 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: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head

        dummy = ListNode(next=head)

        def get_length(head):
            p = head
            length = 0
            while p:
                p = p.next
                length += 1
            return length

        def cut(head, n):
            p = head
            while p and n - 1 > 0:
                p = p.next
                n -= 1
            if p is None:
                return
            new_head = p.next
            p.next = None
            return new_head

        def merge(l1, l2):
            dummy = ListNode(0)
            p = dummy
            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
            if l1:
                p.next = l1
            if l2:
                p.next = l2
            return dummy.next

        length = get_length(head)
        i = 1
        while i < length:
            tail = dummy
            cur = dummy.next
            while cur:
                left = cur
                right = cut(left, i)
                cur = cut(right, i)
                tail.next = merge(left, right)
                while tail.next:
                    tail = tail.next
            i *= 2
        return dummy.next

Explain

该题解使用了自底向上的归并排序算法。首先通过 dummy 节点简化边界情况处理。然后通过 get_length 函数获取链表长度。在归并排序的每一轮中，将链表拆分成若干个长度为 i 的子链表（最后一个子链表长度可能小于 i），并对每对相邻的子链表进行合并。通过 cut 函数将链表切成两半，再通过 merge 函数合并有序链表。不断将 i 乘以 2，对越来越长的有序子链表进行归并，直到整个链表有序。

时间复杂度: O(n * log n)

空间复杂度: O(1)

# 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: ListNode) -> ListNode:
        # 处理空链表或单节点链表的情况
        if head is None or head.next is None:
            return head
        
        # 使用 dummy 节点简化边界情况处理
        dummy = ListNode(next=head)

        def get_length(head):
            p = head
            length = 0
            while p:
                p = p.next
                length += 1
            return length
        
        # 将链表切分成两个子链表
        def cut(head, n):
            p = head
            while p and n - 1 > 0:
                p = p.next
                n -= 1
            if p is None:
                return
            new_head = p.next
            p.next = None
            return new_head
        
        # 合并两个有序链表
        def merge(l1, l2):
            dummy = ListNode(0)
            p = dummy
            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
            if l1:
                p.next = l1
            if l2:
                p.next = l2
            return dummy.next
        
        # 获取链表长度
        length = get_length(head)
        i = 1
        # 自底向上进行归并排序
        while i < length:
            tail = dummy
            cur = dummy.next
            while cur:
                left = cur
                right = cut(left, i)
                cur = cut(right, i)
                tail.next = merge(left, right)
                while tail.next:
                    tail = tail.next
            i *= 2
        return dummy.next

Explore

自底向上的归并排序在链表排序中被选择主要是因为它不依赖于递归调用，从而避免了额外的栈空间消耗，这对于处理大长度链表时更为高效。此外，自底向上的归并排序通过迭代方式逐步扩展子链表的长度，可以更自然地适应链表结构，而不需要像自顶向下那样进行多次链表的切分操作，这些切分操作本身就增加了额外的时间开销。

函数 `cut` 设计用于将链表切分为指定长度的两部分。当链表长度达不到指定的长度时，`cut` 函数会将整个链表作为左侧链表，而右侧链表则为空。具体而言，当遍历完指定长度后，若后续没有更多节点，则返回的 `new_head` 为 `None`，表示右侧子链表不存在，左侧链表包含了所有剩余节点。

在 `merge` 函数中，确保链表稳定性的关键是在比较两个链表节点的值时，当两个节点的值相等时，优先链接左侧链表的节点。这样做保证了在输入链表中具有相同值的节点在输出链表中保持原有的顺序，从而维持了算法的稳定性。

在每一轮归并结束时，可能存在未能与其他子链表合并的尾部子链表。这种情况下，该尾部子链表已经是有序的，可以直接将其连接到当前归并链表的末尾。`tail` 指针用于跟踪当前归并链表的末端，确保无论是完整合并还是简单连接尾部子链表，都能正确维护链表的整体连贯性。