关于leetcode:完虐算法单链表的排序

6次阅读

共计 2371 个字符，预计需要花费 6 分钟才能阅读完成。

更多算法题解，请关注公众号《程序员学长》

LeetCode 148. 排序链表

给定一个节点数为 n 的无序单链表，对其按升序排序。

要求：空间复杂度 O(n)，工夫复杂度 O(nlogn)。

示例：

输出：[-1,0,-2]

返回值：{-2,-1,0}

因为题目要求工夫复杂度是 O(nlogn)，那工夫复杂度是 O(nlogn) 的排序算法有归并排序、疾速排序和堆排序，其中最适宜链表的排序算法是归并排序。

归并排序是基于分治思维，最容易想到的就是自顶向下的递归实现。自顶向下的递归实现次要包含二个环节。

宰割环节
- 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点能够应用快慢指针法，快指针每次挪动 2 步，慢指针每次挪动 1 步，当快指针走到链表的开端时，慢指针恰好指向了链表的中点地位。
- 找到中点后，将链表在中点处宰割成两个子链表。
- 而后递归的进行宰割，直到宰割后的链表只有一个节点或者为 Null。这时，宰割的子链表都是有序的，因为只蕴含一个节点。
合并环节
- 将两个有序的链表合并成一个有序链表。咱们能够采纳双指针法求解。
- 递归执行，直到合并实现。

class Solution:
    def sortList(self, head):
        #如果链表为空或者只蕴含一个节点，递归终止
        if not head or not head.next:
            return head
        #应用快慢指针法来寻找链表的中点
        slow=head
        fast=head.next
        while fast and fast.next:
            fast=fast.next.next
            slow=slow.next
        #slow 指向的就是链表的中点，将链表在中点处进行宰割
        head2=slow.next
        slow.next=None
        #递归的切割宰割链表
        left = self.sortList(head)
        right = self.sortList(head2)
        #合并链表，应用双指针法
        tmp = res = ListNode(0)
        while left and right:
            if left.val < right.val:
                tmp.next=left
                left=left.next
            else:
                tmp.next=right
                right=right.next
            tmp=tmp.next
        if left:
            tmp.next=left
        else:
            tmp.next=right
        return res.next

该算法的工夫复杂度是 O(n)。因为自顶向下是通过递归来实现的，如果思考递归调用栈的栈空间，那么该算法的空间复杂度是 O(logn)。

咱们也能够采纳自底向上的办法来求解。

首先，咱们求出链表的长度 length。而后将链表拆分成子链表进行合并。

咱们用 sublength 示意每次须要排序的子链表的长度，初始时 sublength=1。
每次将链表拆分成若干个长度为 sublength 的子链表（最初一个子链表的长度可能小于 sublength），依照每两个子链表一组进行合并，合并后即能够失去若干个长度为 sublength 2 的有序子链表（最初一个子链表的长度可能小于 sublength 2）。
将 sublength 的值加倍，反复第二步，而后对更长的有序子链表进行合并，直到有序子链表的长度大于或等于链表的长度，这样整个链表的排序就实现了。

咱们来看一下代码的实现。

class Solution:
    def sortList(self, head):
        #合并两个有序链表
        def merge(head1, head2):
            #哨兵节点
            dummyHead = ListNode(0)
            temp=dummyHead

            while head1 and head2:
                if head1.val <= head2.val:
                    temp.next = head1
                    head1 = head1.next
                else:
                    temp.next = head2
                    head2 = head2.next
                temp = temp.next
            if head1:
                temp.next = head1
            else:
                temp.next = head2

            return dummyHead.next

        #如果链表为空，间接返回
        if not head:
            return head
        #遍历一遍链表，求出链表的长度
        length = 0
        node = head
        while node:
            length += 1
            node = node.next

        #创立一个哨兵节点, 指向链表头
        dummyHead = ListNode(0)
        dummyHead.next=head

        #初始时，子链表的长度为 1
        subLength = 1

        while subLength < length:

            prev=dummyHead
            cur=dummyHead.next

            while cur:
                #截取长度为 subLength 的子链表 head1
                head1 = cur
                for i in range(1, subLength):
                    if cur.next:
                        cur = cur.next
                    else:
                        break

                head2 = cur.next
                cur.next = None

                #截取长度为 subLength 的子链表 head2
                cur = head2
                for i in range(1, subLength):
                    if cur and cur.next:
                        cur = cur.next
                    else:
                        break

                #截取完后残余的链表节点
                surplus_head = None
                if cur:
                    surplus_head = cur.next
                    cur.next = None
                #将两个有序链表进行合并
                merged = merge(head1, head2)
                #将排好序的链表插入到新生成的链表里
                prev.next = merged

                #将指针挪动到链表的开端
                while prev.next:
                    prev = prev.next

                #持续合并残余的节点
                cur=surplus_head
            subLength = subLength * 2

        return dummyHead.next

该算法的工夫复杂度是 O(nlogn)，空间复杂度是 O(1)。

正文完