当前位置：首页 > article >正文

【算法】leetcode热题--148.排序链表

article 2024/9/24 20:31:02

https://leetcode.cn/problems/sort-list/description/?envType=study-plan-v2&envId=top-100-liked

问题

需要对于链表进行排序，需要空间复杂度为O1，时间复杂度为Ologn

思路

先考虑时间复杂度，能够实现Ologn的算法就已经没几个了

快排
堆排
归并

快排

首先考虑一下快排。
简单的算法过程是，选中一个点，让其找到最终的排序点位，让左边的都比其小，让右边都比其大。然后让左右两边依次进行递归操作。

正常都是直接选取最左边的点。选定之后，就需要按照算法找到他最终的位置。

问题来了，算法需要通过从向左向右，然后假设出现情况，需要从右向左。链表从左向右没问题，但是从右向左就有问题了。又不是双向链表。

如果需要实现从右向左，需要新开辟一个指针数组，那么这不符合空间复杂度为O1的情况

堆排

这个没什么好说的，这个在数组实现是需要能够做到随机读取的，链表显然做不到。直接pass

归并

归并一开始我认为是并不可以的。因为在正常数组排序之中，他有空间复杂度的开销，一般认为是On 因为在归并的过程之中需要开辟一个新的数组存放。

但在链表之中刚好是不需要这部分开销的。因为在归并构造新的链表时候，只需要将目标结点移动到新的链表尾端即可，这样就没有额外内存开销。这样可以使得归并排序在链表的空间复杂度为O1并且，最后判断两个链表时候，只需要将其与目标链表链接在一起就可以了，而不需要重复循环移动每一个结点

此外归并排序有两种方法，自顶向下与自底向上

一般来说是写自顶向下的，因为这样写法可以直接用递归来写，比较好写代码。但涉及了递归，就不要忘记了递归会产生额外的栈空间的消耗，所以使用自顶向下的归并其实还是有额外空间消耗，即Ologn。所以上文中提及的快排其实也是不行的，也会有栈空闲消耗。

自底向上归并主要想法其实就是与自顶向下相反。
自顶向下就是整个数组先拆两个数组归并，然后两个数组拆成四个数组以此类推。直到我的数组只剩下一个单位，就跟他拆分的那个数组进行归并。

自底向上就是先定下一个subLength表示每一个小数组单元的数值（初始值必定为1）。然后按照这个数值进行分组，两两进行归并。
所以大体的循环框架就出来了：

针对subLength进行循环，直到subLength超过链表长度为止
针对subLength对链表进行分组，然后每两个进行归并操作，直到每一个组别都完成

第一个循环比较好想，第二个循环就比较复杂。

问题1:循环怎么控制？通过什么东西控制？
可以通过一个cur指针进行控制，假设说cur指针为nil就说明已经指向尾部，不需要再进行额外操作。

问题2：怎么进行两个链表裁切工作？
利用当前subLength进行计数裁切就可以了。

问题3:merge完链表插入到哪里？
可以直接开辟一个链表，排序完直接往后面插入就可以了。

// merge两个链表
func merge(head1, head2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    temp, temp1, temp2 := dummyHead, head1, head2
    for temp1 != nil && temp2 != nil {
        if temp1.Val <= temp2.Val {
            temp.Next = temp1
            temp1 = temp1.Next
        } else {
            temp.Next = temp2
            temp2 = temp2.Next
        }
        temp = temp.Next
    }
    // 只要判断一下，然后接入最终的链表就好了，不需要循环复制
    if temp1 != nil {
        temp.Next = temp1
    } else if temp2 != nil {
        temp.Next = temp2
    }
    return dummyHead.Next
}

func sortList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }

    length := 0
    for node := head; node != nil; node = node.Next {
        length++
    }

    dummyHead := &ListNode{Next: head}
    for subLength := 1; subLength < length; subLength <<= 1 {
        prev, cur := dummyHead, dummyHead.Next
        for cur != nil {
            head1 := cur
            for i := 1; i < subLength && cur.Next != nil; i++ {
                cur = cur.Next
            }

            head2 := cur.Next
            cur.Next = nil
            cur = head2
            for i := 1; i < subLength && cur != nil && cur.Next != nil; i++ {
                cur = cur.Next
            }

            var next *ListNode
            if cur != nil {
                next = cur.Next
                cur.Next = nil
            }

            prev.Next = merge(head1, head2)

            for prev.Next != nil {
                prev = prev.Next
            }
            cur = next
        }
    }
    return dummyHead.Next
}