深入理解归并与排序：从Leetcode实践出发（题号21、147、148）

排序是算法设计中最基本的问题之一。很多语言也都内置了排序函数，实际开发中需要手工编写排序函数的情况并不多见。但如果涉及到链表排序的话，通常内置函数就不能直接使用了。事实上，LeetCode题库中有相当多涉及排序的问题，也有很多操作链表的问题，例如：逆转链表（题号#206）、删除链表中倒数第N个结点（题号#19）等。本文主要讨论其中几个把链表和排序结合在一起的问题，并复习一下关于归并排序的知识。本文的题解中涉及很多链表的基本操作，如果读者对链表还不是很熟悉，请参考《算法之美：隐匿在数据结构背后的原理》一书（本书繁体中文版已授权博硕文化出版集团在中国*地区发行）。

探秘算法世界，求索数据结构之道；
汇集经典问题，畅享编程技法之趣；
点拨求职热点，敲开业界名企之门。

本书围绕算法与数据结构这个话题，循序渐进、深入浅出地介绍了现代计算机技术中常用的四十余个经典算法，以及回溯法、分治法、贪婪法和动态规划等算法设计思想。在此过程中，本书也系统地讲解了链表（包括单向链表、单向循环链表和双向循环链表）、栈、队列（包括普通队列和优先级队列）、树（包括二叉树、哈夫曼树、堆、红黑树、AVL树和字典树）、图、集合（包括不相交集）与字典等常用数据结构。同时，通过对22个经典问题（包括约瑟夫环问题、汉诺塔问题、八皇后问题和骑士周游问题等）的讲解，逐步揭开隐匿在数据结构背后的算法原理，力图帮助读者夯实知识储备，激活思维技巧，并最终冲破阻碍编程能力提升的重重藩篱。辅有完整的C++源代码，并穿插介绍了STL中的各种容器。

题目21：Merge Two Sorted Lists

Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

题目要求合并两个有序链表，难度等级为“简单”。而且在《算法之美：隐匿在数据结构背后的原理》一书，还讨论过一样的问题（见如下4.2.3节）。

彼时，我们在书中给出的是采用C++实现的算法，下面给出的参考答案是基于Python3实现的。





class Solution:



    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:



        cur_node = ListNode(0)



        dummy = cur_node



        



        while l1 and l2:



            if  <= :



                cur_node.next = l1



                l1 = l1.next




            else:



                cur_node.next = l2



                l2 = l2.next




            cur_node = cur_node.next




        if l1:



            cur_node.next = l1



        elif l2:



            cur_node.next = l2



            



        return dummy.next

题目147：Insertion Sort List

Given the head of a singly linked list, sort the list using insertion sort, and return the sorted list's head.

LeetCode网站上还贴心地提供了一个动画用以说明插入排序的基本流程，如果你对插入排序本书不是很熟悉，请参考《算法之美：隐匿在数据结构背后的原理》一书中第11章的相关内容。

题解中更多考察的是操作链表的能力，而不是排序算法本身。





class Solution:



    def insertionSortList(self, head: ListNode) -> ListNode:



        dummy = ListNode(-1)



        dummy.next, cur_node = head, head



        



        while cur_node and cur_node.next:



            if cur_node.val <= cur_node.next.val:



                cur_node = cur_node.next




                



            else:



                tmp = cur_node.next




                cur_node.next = cur_node.next.next




                prev = dummy



                while prev.next.val <= :



                    prev = prev.next




                    



                tmp.next = prev.next




                prev.next = tmp



                



        return dummy.next

题目148：Sort List

Given the head of a linked list, return the list after sorting it in ascending order.

Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (. constant space)?

这是第147题的一个升级版，同样是对链表进行排序，但要求算法时间复杂度是O(nlogn)，而插入排序的时间复杂度是 O(n^2) 。下面引用在《算法之美：隐匿在数据结构背后的原理》一书中关于归并排序的一些基本介绍。

基于递归来实现归并排序是比较直观而且容易的，尽管以上描述中都是在讲数组的归并排序，其实转移到链表上，思路也是一样的。





class Solution:



    def sortList(self, head: ListNode) -> ListNode:



        if not head or not head.next: return head



        



        mid = (head)



        left = (head)



        right = (mid)



        



        return (left, right)



    



    



    def midPoint(self, head):



        slow, fast = head, head



        while fast.next and fast.next.next:



            slow = slow.next




            fast = fast.next.next




            



        mid = slow.next




        slow.next = None




        return mid



    



    def merge(self, left, right):



        dummy = cur = ListNode(0)



        while left and right:



            if  < :



                cur.next = left



                cur = cur.next




                left = left.next




            else:



                cur.next = right



                cur = cur.next




                right = right.next




                



        cur.next = left or right



        return dummy.next

对n个记录的序列进行归并排序时，必须进行 $\lceil \log n \rceil$ 趟归并，而每趟归并操作的时间复杂是 O(n) ，所以归并排序算法的时间复杂度是 $O(n\log n)$ 。到此为止，如果能够写出递归实现的链表归并排序代码，题目的难度仍然属于是中等难度。但题目的Follow up是要求实现O(1)的空间复杂度。递归实现的成本就在于逐层递归返回时，需要额外的空间来存储结果，空间复杂度是 $O(\log n)$ 。要真正实现O(1)的空间复杂度，就要设法使用迭代而非递归来实现链表的归并排序，这个代码的实现其实难度等级又上升了一个层次。注意，这个过程跟图11-19所示的二路归并排序算法示意是一致的。基于上述递归代码，我们需要做如下改动：

递归换成迭代，因此找到链表中点的函数midPoint()便不再需要了
归并算法不仅要返回Head指针，还要返回Tail指针，这是为了后续的组合拼接
还需要一个函数split()，它把输入的链表分成两部分，一部分是开始的n个结点，剩余的结点作为第二部分





class Solution:



    def sortList(self, head: ListNode) -> ListNode:



        if not head or not head.next: return head



        



        size, interval, cur = 0, 1, head



        while cur:



            size += 1




            cur = cur.next




            



        dummy = ListNode(-1)



        dummy.next = head



        while interval < size:



            cur = dummy.next




            tail = dummy



            



            while cur:



                l = cur



                r = (l, interval)



                cur = (r, interval)



                m0, m1 = (l, r)



                tail.next = m0



                tail = m1



            interval <<= 1




        



        return dummy.next




    



    #splits the list into 2 parts, first n elements and the rest




    def split(self, head: ListNode, size: int) -> ListNode:



        rest = head



        while rest and size > 0:



            size -= 1




            head = rest



            rest = rest.next




        if head:



            head.next = None




        return rest



    



    def merge(self, left, right):



        dummy = cur = ListNode(0)



        while left and right:



            if  < :



                cur.next = left



                cur = cur.next




                left = left.next




            else:



                cur.next = right



                cur = cur.next




                right = right.next




                



        cur.next = left or right



        ## Return both head and tail




        while cur.next:



            cur = cur.next




        return dummy.next, cur

【本文完】

秒客网

深入理解归并与排序：从Leetcode实践出发（题号21、147、148）

题目21：Merge Two Sorted Lists

题目147：Insertion Sort List

题目148：Sort List

相关文章