题目链接

力扣

题目描述

给定链表的头结点 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 * 104] 内
-105 <= Node.val <= 105
 

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

解题思路

1. 熟悉归并排序的同学应该知道，若采用自底向上归并，可以把递归调用改为迭代，不使用额外空间
2. 对于链表，可以把只有1个节点的链表看作有序，即归并的底
3. 两个长度为1的链表合并为长度为2的有序链表，两个长度为2的链表合并为长度为4的有序链表，以此类推
4. 设归并长度为len，一开始len=1，每进行一轮归并，len*=2，当len>=原始链表长度时，链表排序完成
5. 由于链表始终不能断开，因此merge方法中不能用null来判断是否合并完一条链表
6. merge方法设计为void Merge(ListNode beforeHead, ListNode mid, ListNode afterTail)        

• beforehead用于确定head1和合并的指针位置
• mid是链表2的开始head2，同时也是链表1的结尾哨兵
• afterTail是链表2的结尾哨兵

如何确定每次合并的3个参数？

• 对每个len的首次合并，beforeHead为链表头部之前的哨兵节点
• mid为beforeHead后面的第len+1个节点
• afterTail为mid后面的第len个节点
• 使用上述参数完成一个区间的合并
• 下一个区间的beforeHead为beforeHead后面的第len*2个节点
• 以上移动均需注意是否达到链表尾部的null
• 若beforeHead为null，本轮合并完成

时间复杂度O(nlogn)，空间复杂度O(1)，只使用了几个变量和1层函数调用

代码

Python

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head
        n = 0
        dummy = ListNode(next=head)
        cur = head
        while cur:
            cur = cur.next
            n += 1
        len = 1
        while len < n:
            beforeHead = dummy
            while beforeHead:
                mid = beforeHead.next
                for _ in range(len):
                    if mid:
                        mid = mid.next
                    else:
                        break
                afterTail = mid
                for _ in range(len):
                    if afterTail:
                        afterTail = afterTail.next
                    else:
                        break
                self.Merge(beforeHead, mid, afterTail)
                for _ in range(len * 2):
                    if beforeHead:
                        beforeHead = beforeHead.next
                    else:
                        break
            len *= 2
        return dummy.next

    def Merge(self, beforeHead: ListNode, mid: ListNode, afterTail: ListNode):
        cur = beforeHead
        head1 = cur.next
        head2 = mid
        while head1 != mid and head2 != afterTail:
            if head1.val <= head2.val:
                cur.next = head1
                head1 = head1.next
            else:
                cur.next = head2
                head2 = head2.next
            cur = cur.next
        while head1 != mid:
            cur.next = head1
            head1 = head1.next
            cur = cur.next
        while head2 != afterTail:
            cur.next = head2
            head2 = head2.next
            cur = cur.next
        cur.next = afterTail