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]。全部代码如下所示。

Read more

876. 链表的中间结点

题目描述 给定一个带有头结点 head 的非空单链表,返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 示例 1: 输入:[1,2,3,4,5] 输出:此列表中的结点 3 (序列化形式:[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意,我们返回了一个 ListNode 类型的对象 ans,这样: ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL. 示例 2: 输入:[1,2,3,4,5,6] 输出:此列表中的结点 4 (序列化形式:[4,5,6]) 由于该列表有两个中间结点,值分别为 3 和 4,我们返回第二个结点。 https://leetcode-cn.com/problems/middle-of-the-linked-list/ 解法1 顺序遍历一次求得链表长度为n,然后从头遍历n/2个节点即为答案 解法2 解法2称为快慢指针法,快指针一次遍历两个节点,慢指针一次遍历一个节点。当快指针遍历到链表尽头时,慢指针指向的位置即为链表的中间节点。该方法只需要访问链表一次,十分精妙。快慢指针法也可被用来判断链表是否存在环路:Floyd判圈算法。链表的归并排序算法的实现也依赖于该方法寻找链表中间节点。

Read more

146. LRU缓存机制

题目描述 运用你所掌握的数据结构,设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。 获取数据 get(key) – 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。写入数据 put(key, value) – 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。 进阶: 你是否可以在 O(1) 时间复杂度内完成这两种操作? 示例: LRUCache cache = new LRUCache( 2 /* 缓存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得密钥 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得密钥 1 作废 cache.get(1); // 返回 -1…

Read more

61. 旋转链表

题目描述 给定一个链表,旋转链表,将链表每个节点向右移动 k 个位置,其中 k 是非负数。 示例 1: 输入: 1->2->3->4->5->NULL, k = 2 输出: 4->5->1->2->3->NULL 解释: 向右旋转 1 步: 5->1->2->3->4->NULL 向右旋转 2 步: 4->5->1->2->3->NULL 示例 2: 输入: 0->1->2->NULL, k = 4 输出: 2->0->1->NULL 解释: 向右旋转 1 步: 2->0->1->NULL 向右旋转 2 步: 1->2->0->NULL 向右旋转 3 步: 0->1->2->NULL 向右旋转 4 步: 2->0->1->NULL https://leetcode-cn.com/problems/rotate-list/ 解法1 题目要求移动链表的k个元素,我们不妨先考虑只移动一个元素的情况。对于除了最后一个节点外的每个节点,我们都做以下动作。 备份下一个节点的值 将上一个节点的值覆盖到下一个节点 下一个节点的值作为“新的上一个节点的值” 移动到下一个节点 如果遇到最后一个节点,则将该节点的值覆盖到第一个节点上。下面我们用图来描述以下过程,下图以“1->2->3->4->5->NULL”为例。 上面的图描述了移动一个节点后的结果,当p指向倒数第二个节点时循环终止,此时nextBak=5。循环结束后,我们用nextBak覆盖掉头节点的值就完成了移动一个节点的过程。 我们还可以做一个优化,这个优化很容易想到。当移动次数k超过链表长度n时,我们只需要移动n%k个位置即可。下面的代码实现了上述全部过程。 解法2 上面的算法如果使用了优化,最多要移动n-1次单个元素。而移动单个元素的代价是移动链表中所有的元素,也就是n。因此,解法1的时间复杂度为O(n^2)。我们能不能只移动一次,来降低时间复杂度呢? 我们通过计算找到链表的一个“切点”(图3的…

Read more

23. 合并K个排序链表

题目描述 合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。 示例: 输入: [   1->4->5,   1->3->4,   2->6 ] 输出: 1->1->2->3->4->4->5->6 https://leetcode-cn.com/problems/merge-k-sorted-lists/ 解法1 题目要求合并K个有序链表, 我们不妨先考虑合并两个有序链表. 为了便于操作, 我们创建一个头节点head, 该节点的value字段没有意义. 待合并的两个链表分别记为l1与l2, 为了保持合并后的链表仍然有序, 我们每次都从l1与l2中挑选当前最小的节点, 然后将其插入到头节点head. 现有链表l1, l2, 头节点head p = head if (l1.val < l2.val) { // 选取l1, l2当前最小的节点 p.next = l1; l1 = l1.next; } else { p.next = l2; l2 = l2.next; }…

Read more

2. 两数相加

题目描述 给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外,这两个数都不会以 0 开头。 示例: 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807 https://leetcode-cn.com/problems/add-two-numbers/ 思路1 首先链表是倒叙的,这就启发了我们可以用按位相加的方法逐步地求得结果。链表l1与l2相加,对应位相加后大于10,我们需要向前进位。下面的实现思路较为清晰,且易理解,但是有点笨拙。因为这涉及了三次的链表扫描。 直接将l1与l2对应位相加 扫描相加后的结果,如果大于等于10,向前进位 重新扫描,将添加的多余节点剔除 对于这种解法涉及到3次扫描,运行时间为29ms,“我的提交执行用时已经战胜 93.99 % 的 java 提交记录”。我们还有优化的空间,争取一次扫描就能够完成计算。 思路2 我们能不能只用一个while循环就实现整个算法所需要的流程呢?我们使用while循环,条件为链表l1与l2任意之一遍历到尽头。在while内部有三种可能 l1与l2均未遍历到尽头 只有l1未遍历到尽头 只有l2未遍历到尽头 对于情况1,我们只需要将相应位置到数相加,保存的新建的链表节点中即可。需要注意的是,我们不能直接使用“=”覆盖新建链表节点到val字段,而是应该使用“+=”操作符。这样做是为了利用上,上次循环产生到进位符。对于情况2与3,我们用上次进位符与l1或l2到节点值相加即可。 为了处理相加后可能产生的进位情况,我们在后面判断新建节点的值是否大于等于10.若大于等于10,下一个新建的节点赋予初值1,否则赋初值0.

Read more