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

单链表的排序

问题形容

LeetCode 148. 排序链表

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

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

示例：

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

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

剖析问题

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

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

  1. 宰割环节

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

  2. 合并环节

    • 将两个有序的链表合并成一个有序链表。咱们能够采纳双指针法求解。
    • 递归执行，直到合并实现。

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。而后将链表拆分成子链表进行合并。

  1. 咱们用sublength示意每次须要排序的子链表的长度，初始时sublength=1。
  2. 每次将链表拆分成若干个长度为sublength的子链表（最初一个子链表的长度可能小于sublength），依照每两个子链表一组进行合并，合并后即能够失去若干个长度为sublength 2的有序子链表（最初一个子链表的长度可能小于sublength 2）。
  3. 将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)。