-
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 https://leetcode-cn.com/problems/sort-list/ 解法1 – 自顶向下的归并排序 首先，时间复杂度限定O(nlogn)，那么在常见的排序算法中，可选的排序算法只有快排、堆排序和归并排序。因为采用了链表这种数据结构，快排和堆排序需要随机访问，因此归并排序较为合适。此外，题目要求常熟级的空间复杂度，也就是说要求原地排序，我们就不能将链表转化为数组排序后再转化为链表。我们在这里贴出常见的排序算法以及相应的空间/时间复杂度。 归并排序分为自顶向下和自底向上两种实现方式，自顶向下需要使用递归来把待排序的数组拆分成两部分，这个过程持续直到待拆分的元素只剩下一个，这一个元素当然是排序好的了。然后我们逐层返回，将排序好的两部分归并，那么归并后的链表也是有序的。严格地说，自顶向下的归并排序并不是常数级空间复杂度，因为递归过程中消耗了系统栈。 下面以示例1: 4->2->1->3为例，图解自顶向下的归并排序过程。为了将链表分为相等的两部分，我们需要寻找链表的中间节点。在这里我们使用了一个技巧，只需要遍历一遍链表就能找到中间节点。 我们寻找到中间节点，记为mid。我们还需要找到中间节点的前一个节点midPrev，因为我们需要将链表断开形成左右两个独立的链表。如果不断开，在寻找中间节点的过程会形成无限递归！！！ [4->2->1->3]会被拆分成[4->2], [1->3]两部分，而[4->2]又会被拆分成[4]和[2]两部分。当链表只剩下一个元素时，自然就是排好序的。我们再返回到上一层，将排好序的元素归并。[4]与[2]归并后会形成[2->4]的链表，而[1]与[3]归并会形成[1->3]的链表，我们再返回更上一层将[2->4]与[1->3]归并得到最终结果[1->2->3->4]。全部代码如下所示。
-
109. 有序链表转换二叉搜索树
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定的有序链表： [-10, -3, 0, 5, 9], 一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5 https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/ 解法1 二叉搜索树(BST)是一种特殊的二叉树，他满足左子树的全部元素都小于根节点，右子树的全部元素都大于根节点。题目另外要求生成的平衡的BST，意味着在上面的基础上又添加了新条件：左右子树高度差的绝对值不超过1。 首先给定的链表是有序的，加上BST本身的特性会使我们联想到二分查找的思想。根据有序列表构建BST我们可以使用类似于二分查找的思路，用中心元素将链表划分为两部分，左半部分都小于中心元素、右半部分都大于中心元素。 采用链表作为数据结构，不容易实现随机访问。为了能够快速的获取中心元素，我们首先将链表转换为数组。我们取数组长度的一半作为中心元素的索引。中心元素作为二叉树的根节点，将左半部分与右半部分以相同的方式处理继续构建左子树与右子树。直到左半部分或右半部分没有元素时，构建过程停止。 下面以题目以“[-10, -3, 0, 5, 9]”为例，构建BST。下面的图片给出了两颗BST，他们都是合法的，但我们的处理逻辑仅能够产生左边的形态。 我们列举BST的构建过程来说明，为什么我们的逻辑只能够产生左边的形态。首先，说明下我们采用的边界都是左闭右开的形式。arr=[-10, -3, 0, 5, 9]。|arr|=5, mid = (0+5)/2 = 2,取arr[2]=0作为中间元素，左半部分为[-10, -3]，右半部分为[5, 9]。我们继续利用左半部分构建根节点0的左子树。计算|[-10, -3]| = 2，mid = (0+2)/2 = 1，取arr[1]=-3作为根节点。我们可以看到，因为左子树仅有两个元素，按照我们mid=(左边界索引+右边界索引)/2的处理方式会将第二个元素-3作为子树的根节点，而不是-10作为根节点。…