难度:Eazy
面试题 02.02. 返回倒数第 k 个节点
实现一种算法,找出单向链表中倒数第 k 个节点。返回该节点的值。
注意:本题相对原题稍作改动
示例:
输入: 1->2->3->4->5 和 k = 2
输出: 4
说明: 给定的 k 保证是有效的。
思路1:两次遍历
1.第一次遍历数组,统计链表中元素个数Count
2.第二次遍历数组,用Pos表示当前元素位置,当Pos = Count - K时,return val
1 |
|
思路2:双指针
1.令指针p先走k步
2.令指针q = head
3.q = q.next, p = p.next,当p == null,返回q
1 |
|
面试题 02.03. 删除中间节点
实现一种算法,删除单向链表中间的某个节点(即不是第一个或最后一个节点),假定你只能访问该节点。
示例:
输入:单向链表a->b->c->d->e->f中的节点c
结果:不返回任何数据,但该链表变为a->b->d->e->f
思路:因为删除的既不是第一个节点也不是最后一个节点,所以可以保证 待删除节点的后继节点不为空,所以仅需将该节点的值设为后继节点的值,并将该节点的的next
设置为该节点的后继节点的后继节点
即可。
1 |
|
21. 合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
思路:创建新节点head
,设置l1和l2分别代表两个待合并链表的头部,比较l1和l2的大小,将较小元素设置为head.next && head = head.next
,同时较小节点的指针后移。
1 |
|
234. 回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
示例 2:
输入: 1->2->2->1
输出: true
进阶:
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?
思路1:
双端队列。
1 |
|
思路2:
快慢指针。注意,这段代码及其优雅。这里面包括了几个常用技巧:
1、在使用快慢指针时,若链表长度为偶数,则慢指针指向len(list)/2 + 1
个节点,若链表长度为奇数,则指向中间节点:
1 -> 2 -> 3 -> 4中,指向3
1 -> 2 -> 3 -> 4 ->5中,指向3
2、若节点个数为奇数,则slow指针需要 = slow.next
,以保证slow指针和fast指针的初始节点相同
3、翻转链表时,需要先定义头结点为null,同时定义后继节点为tmp
1 |
|
剑指 Offer 18. 删除链表的节点
给定单向链表的头指针和一个要删除的节点的值,定义一个函数删除该节点。
返回删除后的链表的头节点。
注意:此题对比原题有改动
示例 1:
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点,那么在调用了你的函数之后,该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], val = 1
输出: [4,5,9] 解释: 给定你链表中值为 1 的第三个节点,那么在调用了你的函数之后,该链表应变为 4 -> 5 -> 9.
思路:依次遍历,设置前驱结点pre,当cur节点的值等于val时,pre = cur.next
即可。
1 |
|
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,我们返回第二个结点。
思路:快慢指针,非常容易,不再介绍。
1 |
|
203. 移除链表元素
删除链表中等于给定值 val 的所有节点。
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
思路:简单遍历,找到val后用while去除所有重复元素即可。
1 |
|
剑指 Offer 52. 两个链表的第一个公共节点
输入两个链表,找出它们的第一个公共节点。
示例 1:
输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出:Reference of the node with value = 8
输入解释:相交节点的值为 8 (注意,如果两个列表相交则不能为 0)。从各自的表头开始算起,链表 A 为 [4,1,8,4,5],链表 B 为 [5,0,1,8,4,5]。在 A 中,相交节点前有 2 个节点;在 B 中,相交节点前有 3 个节点。
『优 雅 警 告 !』
1 |
|
206. 反转链表
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
1 |
|
1290. 二进制链表转整数
给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
示例 1:
输入:head = [1,0,1]
输出:5
解释:二进制数 (101) 转化为十进制数 (5)
示例 2:
输入:head = [0]
输出:0
示例 3:
输入:head = [1]
输出:1
示例 4:
输入:head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出:18880
示例 5:
输入:head = [0,0]
输出:0
思路: 利用Integer
中的parseInt(sb.toString(), 2)
将2进制string
转化为10进制int
1 |
|
141. 环形链表
给定一个链表,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。 否则,返回 false 。
进阶:
你能用 O(1)(即,常量)内存解决此问题吗?
思路1:
1 |
|
思路2:取巧
1 |
|
面试题 02.01. 移除重复节点
编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。
示例1:
输入:[1, 2, 3, 3, 2, 1]
输出:[1, 2, 3] 示例2:
输入:[1, 1, 1, 1, 2]
输出:[1, 2]
提示:
链表长度在[0, 20000]范围内。 链表元素在[0, 20000]范围内。
1 |
|
1474. 删除链表 M 个节点之后的 N 个节点
给定链表 head 和两个整数 m 和 n. 遍历该链表并按照如下方式删除节点:
开始时以头节点作为当前节点. 保留以当前节点开始的前 m 个节点. 删除接下来的 n 个节点. 重复步骤 2 和 3, 直到到达链表结尾. 在删除了指定结点之后, 返回修改过后的链表的头节点.
进阶问题: 你能通过就地修改链表的方式解决这个问题吗?
示例 1:
输入: head = [1,2,3,4,5,6,7,8,9,10,11,12,13], m = 2, n = 3
输出: [1,2,6,7,11,12]
解析: 保留前(m = 2)个结点, 也就是以黑色节点表示的从链表头结点开始的结点(1 ->2).
删除接下来的(n = 3)个结点(3 -> 4 -> 5), 在图中以红色结点表示.
继续相同的操作, 直到链表的末尾.
返回删除结点之后的链表的头结点.
示例 2:
输入: head = [1,2,3,4,5,6,7,8,9,10,11], m = 1, n = 3
输出: [1,5,9]
解析: 返回删除结点之后的链表的头结点.
示例 3:
输入: head = [1,2,3,4,5,6,7,8,9,10,11], m = 3, n = 1
输出: [1,2,3,5,6,7,9,10,11]
示例 4:
输入: head = [9,3,7,7,9,10,8,2], m = 1, n = 2
输出: [9,7,8]
思路:简单模拟
1 |
|
难度:Medium
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
思路:
1、首先计算链表中节点数目为count,使k = count % k
,这样可以减少很多不必要的计算。
2、将原问题转换为:将倒数k个节点移动至节点头部。
3、依次遍历数组,将第count - k个节点的next
指针指向null,再将head节点设置为count - k + 1,当遍历至原链表尾部时,将尾部节点的next指向原链表的头部即可。
1 |
|
369. 给单链表加一
用一个 非空 单链表来表示一个非负整数,然后将这个整数加一。
你可以假设这个整数除了 0 本身,没有任何前导的 0。
这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。
示例:
输入: [1,2,3]
输出: [1,2,4]
思路: 这道题我采用的思路比较简单,就是先用一个栈保存链表中的所有元素,然后依次出栈(第一次出栈的元素 + 1)
,之后用carry 和 sum 保存进位和总和,逢使10进1,最后翻转链表即可。
1 |
|
445. 两数相加 II
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
进阶:
如果输入链表不能修改该如何处理?换句话说,你不能对列表中的节点进行翻转。
示例:
输入:(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 8 -> 0 -> 7
思路:这道题的思路跟上一道题非常相似,也是先进栈,然后依次出栈,逢10进1,区别是:
- 将上一题的单个链表转化成了两个链表。
- 最后的结果不需要翻转。
1 |
|
24. 两两交换链表中的节点
给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
思路:这道题思路上比较简单,主要考察的是链表操作的基本功,依次两两交换即可。
1 |
|
143. 重排链表
给定一个单链表 L:L0→L1→…→Ln-1→Ln , 将其重新排列后变为: L0→Ln→L1→Ln-1→L2→Ln-2→…
你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。
示例 1:
给定链表 1->2->3->4, 重新排列为 1->4->2->3.
示例 2:
给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
思路:这道题考察的知识点比较多,先用快慢指针将链表断开,然后reverse链表的后半部分,最后合并链表。
1 |
|
82. 删除排序链表中的重复元素 II
给定一个排序链表,删除所有含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。
示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:
输入: 1->1->1->2->3
输出: 2->3
思路:建立虚拟头结点pre,依次遍历链表,若pre.next.val == pre.next.next.val
,则证明出现了重复节点,此时只要在pre.next.next
之后找到node.val != pre.next.val
的节点,再将pre.next = val
即可跳过所有重复节点。
1 |
|
725. 分隔链表
给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。
每部分的长度应该尽可能的相等: 任意两部分的长度差距不能超过 1,也就是说可能有些部分为 null。
这k个部分应该按照在链表中出现的顺序进行输出,并且排在前面的部分的长度应该大于或等于后面的长度。
返回一个符合上述规则的链表的列表。
举例: 1->2->3->4, k = 5 // 5 结果 [ [1], [2], [3], [4], null ]
示例 1:
输入: root = [1, 2, 3], k = 5
输出: [[1],[2],[3],[],[]] 解释:输入输出各部分都应该是链表,而不是数组。
例如, 输入的结点 root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一个输出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一个元素 output[4] 为 null, 它代表了最后一个部分为空链表。
示例 2:
输入: root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
输出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解释:
输入被分成了几个连续的部分,并且每部分的长度相差不超过1.前面部分的长度大于等于后面部分的长度。
思路:这道题当时想了很久,总结关键点如下:
- 统计链表的长度count,则每个部分应该含有
count / k
个节点,如 假设count = 11
,k = 3
,那么每部分应该含有11 / 3 = 3(向下取整)
个节点,剩下的11 - 3 * 3 = 2
个节点代表前2个分段应该多包含1个节点
以下代码是我纯手打,一遍AC的,太爽了!
1 |
|
142. 环形链表 II
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意,pos 仅仅是用于标识环的情况,并不会作为参数传递到函数中。
说明:不允许修改给定的链表。
进阶:
- 你是否可以使用 O(1) 空间解决此题?
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。
示例 2:
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。
示例 3:
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。
提示:
- 链表中节点的数目范围在范围 [0, 104] 内
- -105 <= Node.val <= 105
- pos 的值为 -1 或者链表中的一个有效索引
思路: 我也不知道这道题为啥能当Medium,我感觉和Eazy毫无区别。
1 |
|
328. 奇偶链表
给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1),时间复杂度应为 O(nodes),nodes 为节点总数。
示例 1:
输入: 1->2->3->4->5->NULL
输出: 1->3->5->2->4->NULL
示例 2:
输入: 2->1->3->5->6->4->7->NULL
输出: 2->3->6->7->1->5->4->NULL
说明:
- 应当保持奇数节点和偶数节点的相对顺序。
- 链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。
思路: 这道题最开始的思路是先遍历完所有的奇数节点,再遍历偶数节点,最后进行拼接,可后来发现,当所有的奇数节点的指针都指向下一个奇数节点时,已经无法对偶数节点进行遍历(因为前驱结点已经消失,相当于把偶数节点删除了)。后来经过研究,发现可以同时遍历奇数节点和偶数节点,问题解决,以下代码一遍AC。
1 |
|
面试题 02.04. 分割链表
编写程序以 x 为基准分割链表,使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x,x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可,其不需要被置于左右两部分之间。
示例:
输入: head = 3->5->8->5->10->2->1, x = 5
输出: 3->1->2->10->5->5->8
思路:
由于链表中的节点是无序的,所以原地排序的难度很高,暂时想不出解决方案。所以目前的思路是new
两个头结点,将node.val < x
的节点放在head1
后,将node.val >= x
的节点放在head2
后,最后再将head2和head1
连接起来即可。
哭了哭了哭了,有感觉了,有感觉了,这道题又是1遍AC100%,酬勤酬勤。
1 |
|
1019. 链表中的下一个更大节点
给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为:node_1, node_2, node_3, … 。
每个节点都可能有下一个更大值(next larger value):对于 node_i,如果其 next_larger(node_i) 是 node_j.val,那么就有 j > i 且 node_j.val > node_i.val,而 j 是可能的选项中最小的那个。如果不存在这样的 j,那么下一个更大值为 0 。
返回整数答案数组 answer,其中 answer[i] = next_larger(node_{i+1}) 。
注意:在下面的示例中,诸如 [2,1,5] 这样的输入(不是输出)是链表的序列化表示,其头节点的值为 2,第二个节点值为 1,第三个节点值为 5 。
示例 1:
输入:[2,1,5]
输出:[5,5,0]
示例 2:
输入:[2,7,4,3,5]
输出:[7,0,5,5,0]
示例 3:
输入:[1,7,5,1,9,2,5,1]
输出:[7,9,9,9,0,5,0,0]
提示:
- 对于链表中的每个节点,1 <= node.val <= 10^9
- 给定列表的长度在 [0, 10000] 范围内
思路:感觉这题除了暴力想不出其他的办法,但是暴力算法的代码不够优雅,所以就先放在这里吧,日后想到其他的办法再来填坑。(看了题解貌似用单调栈可以解决,最近2道题都用了单调栈,感觉自己掌握的不是很好,等刷完了树
就来啃这块骨头)
92. 反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明: 1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
思路: 不多说了, E A Z Y 就完事儿了。(我开玩笑的,这题挺难的,我一开始看错题了)
1 |
|
19. 删除链表的倒数第N个节点
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
说明:
给定的 n 保证是有效的。
进阶:
- 你能尝试使用一趟扫描实现吗?
思路:first节点先走n步,second节点设为head,之后同时= *.next
即可。
1 |
|
1171. 从链表中删去总和值为零的连续节点
给你一个链表的头节点 head,请你编写代码,反复删去链表中由 总和 值为 0 的连续节点组成的序列,直到不存在这样的序列为止。
删除完毕后,请你返回最终结果链表的头节点。
你可以返回任何满足题目要求的答案。
(注意,下面示例中的所有序列,都是对 ListNode 对象序列化的表示。)
示例 1:
输入:head = [1,2,-3,3,1]
输出:[3,1]
提示:答案 [1,2,1] 也是正确的。
示例 2:
输入:head = [1,2,3,-3,4]
输出:[1,2,4]
示例 3:
输入:head = [1,2,3,-3,-2]
输出:[1]
思路:用一个map保存所有前项的 和 and
链表节点。遍历节点,若当前 和 and
map中保存的 sum
不同,则该节点的 next
指向 map中的节点。
1 |
|
总结
原本想都写完的,但今天是在是太累了,有时间再写Medium吧~。在写这篇文章的过程中,重新将链表的Eazy题目做了一遍,这个过程明显比一周前要顺利的多,很多道题用了比之前更加优雅的代码,也算有了成长。
If you are not proud of it , it’s not enough.
More Details:Setting up your GitHub Pages site locally with Jekyll