Loading... 148、排序链表 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 示例 1: ``` 输入: 4->2->1->3 输出: 1->2->3->4 ``` 示例 2: ``` 输入: -1->5->3->4->0 输出: -1->0->3->4->5 ``` 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ## 标签 `归并排序`， `双路归并`，`双指针` ## 算法 需要满足` O(n log n) `时间复杂度，想到的是归并排序 我是看题目评论和文章讲解知道的，向算法大佬们学习 刷题之后，总结写文，印象比较深刻 在数组中的归并排序，我们需要找到一个中点，然后一分为二 继续找中点，一分为二 .... 直到分到不能再分为止 ## 双指针 所以，遇到的第一个小问题就是，中点怎么找？ 使用`双指针` 一个`slow`指针，一个`fast`指针，`slow`指针走一步，`fast`走两步 当`fast`走完时，`slow`所在位置即链表的中点 ## 归并排序 找到中点后，我们就可以使用`归并排序` 这里使用递归来完成这个操作 递归三要素，走你 1、寻找递归结束条件 2、明白每次递归做什么 3、找出函数的等价关系式 一个一个来 - 结束条件是什么？ 目的就是让他分到不能再分为止，所以结束条件就是，当前节点为空，则返回 - 每次递归都做了什么？ 每次递归都将当前链表按中点一分为二，返回一个由自身左链表和右链表构成的有序链表 函数的等价关系式是什么？ 左边节点`1` 右边节点`2` 向上合并就是`12` 所以等价关系式为 当前链表 = 左边链表 + 右边链表 f(new_node) = f(node.left) + f(node.right) 再解释下，就是`左边排好序的链表` 与 `右边排好序的链表`归并 下一个小问题就是，如何让两个有序链表合并成一个有序链表 可以做下面练习题，大佬们叫这个方法为`双路归并` 练习题【合并两个有序链表】： <https://leetcode-cn.com/problems/merge-two-sorted-lists/> ## 代码 ```python class Solution: def sortList(self, head: ListNode) -> ListNode: # 判断是否分都底 if not head and not head.next: return head slow = head fast = head.next # 双指针，获取中点 while fast and fast.next: slow = slow.next fast = fast.next.next # 以中点为界，断开分成两个链表 right_list = slow.next slow.next = None left_list = head # 对两个链表进行递归排序，最终拿到左有序链表 与 右有序链表 sorted_left = self.sortList(left_list) sorted_right = self.sortList(right_list) # 新建一个头节点 dummy_head = ListNode(-1) cur = dummy_head # 归并 while sorted_left and sorted_right: if sorted_left.val < sorted_right.val: cur.next = sorted_left sorted_left = sorted_left.next else: cur.next = sorted_right sorted_right = sorted_right.next cur = cur.next # 上方循环结束后，必定有一个没有被遍历到 # 所以判断一下，补上最后一个节点 if sorted_left: cur.next = sorted_left else: cur.next = sorted_right # 返回已排序链表 return dummy_head.next ``` ```java /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode r = slow.next; slow.next = null; ListNode sortedLeft = sortList(head); ListNode sortedRight = sortList(r); ListNode dummyHead = new ListNode(-1); ListNode cur = dummyHead; while (sortedLeft != null && sortedRight != null) { if (sortedLeft.val < sortedRight.val) { cur.next = sortedLeft; sortedLeft = sortedLeft.next; } else { cur.next = sortedRight; sortedRight = sortedRight.next; } cur = cur.next; } if (sortedLeft == null) { cur.next = sortedRight; } else { cur.next = sortedLeft; } return dummyHead.next; } } ``` Last modification：April 10th, 2020 at 10:13 pm © 允许规范转载