共计 4748 个字符,预计需要花费 12 分钟才能阅读完成。
链表
链表是数据结构里一个很根底然而又很爱考的线性构造,链表的操作相对来说比较简单,然而非常适合考查面试者写代码的能力,以及对 corner case 的解决,还有指针的利用很容易引起 NPE (null pointer exception)。综合以上起因,链表在面试中很重要。
提到链表就不得不提数组,它和数组能够说是数据结构的根底,那么它们最次要的区别在于:
- 数组在物理内存上必须是间断的
- 链表在物理内存上不须要间断,通过指针连贯
所以数组最好的性质就是能够随机拜访 random access,有了 index,能够 O(1) 的工夫拜访到元素。
而链表因为不间断,所以无奈 O(1) 的工夫定位任意一个元素的地位,那么就只能从头开始遍历。
这就造成了它们之间增删改查上效率的不同。
除此之外,链表自身的构造与数组也是齐全不同的。
LinkedList 是由 ListNode 来实现的:
class ListNode {
int value;
ListNode next;
}
构造上长这样:
这是单向链表,那还有的链表是双向链表,也就是还有一个 previous pointer 指向以后 node 的前一个 node:
class ListNode {
int value;
ListNode next;
ListNode prev;
}
其实链表相干的题目没有很难的,套路也就这么几个,其中最常考最根底的题目是反转链表,据说微软能够用这道题电面刷掉一半的 candidate,两种办法一遍 bug free 还是不容易的。文章之前曾经写过了,点击这里中转温习。
明天咱们来说链表中 最次要的 2 个技巧 : 双指针法 和 dummy node,置信看完本文后,链表相干的绝大多数题目你都能搞定啦。
双指针法
双指针法在很多数据结构和题型中都有利用,在链表中用的最多的还是 快慢指针
。
顾名思义,两个指针一个走得快,一个走得慢,这样的益处就是以不同的速度遍历链表,不便找到指标地位。
常见的问题比方找一个链表的中点,或者判断一个链表是否有环。
例 1:找中点
这题就是给一个链表,而后找到它的中点,如果是奇数个很好办,如果是偶数个,题目要求返回第二个。
比方:
1 -> 2 -> 3 -> 4 -> 5 -> NULL,须要返回 3 这个 ListNode;
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL,须要返回 4 这个 ListNode。
但其实吐槽一下,如果真的要设计一个这样的 API,我更偏向于抉择返回偶数个中的第一个中点。
为什么呢?
算法题都是工业生产中一些问题的形象。比如说咱们找中点的目标是为了把这个链表断开,那么返回了 3,我能够断开 3 和 4;然而返回了 4,单向链表我怎么断开 4 之前的中央呢?还得再来一遍,麻烦。
Solution
办法一、
这题最直观的解法就是能够先求这个链表的长度,而后再走这个长度的一半,失去中点。
class Solution {public ListNode middleNode(ListNode head) {if(head == null) {return null;}
int len = 0;
ListNode current = head;
while(current != null) {
len++;
current = current.next;
}
len /= 2;
ListNode result = head;
while(len > 0) {
result = result.next;
len--;
}
return result;
}
}
办法二、快慢指针
咱们用两个指针一起来遍历这个链表,每次快指针走 2 步,慢指针走 1 步,这样当快指针走到头的时候,慢指针应该刚好在链表的中点。
class Solution {public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
这两个办法孰优孰劣呢?
网上很多说什么办法一过了两遍链表,办法二只过了一遍。
但其实,然而办法二用了两个指针来遍历,所以两个办法过的遍数都是一样的。
它们最大的区别是:
办法一是 offline algorithm,办法二是 online algorithm。
公司里的数据量是源源不断的,比方电商零碎里总有客户在下单,社交软件里的好友增长是始终在涨的,这些是数据流 data stream,咱们是无奈计算数据流的长度的。
那么 online algorithm 可能给时刻给出以后的后果,不用说等数据全副录入实现后,实际上也录不完。。这是 online algorithm 比 offline algorithm 大大的劣势所在。
更多的解释大家能够参考 stack overflow 的这个问题,链接在文末。
例 2:判断单链表是否有环
思路:快慢指针一起从 head 登程,每次快指针走 2 步,慢指针只走 1 步,如果存在环,那么两个指针肯定会相遇。
这题是典型的龟兔赛跑,或者说在操场跑圈时,跑的快的同学总会 套圈 跑的慢的。
public class Solution {public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if(slow == fast) {return true;}
}
return false;
}
}
这题有个升级版,就是要求返回环的终点。
例 3:返回有环链表的环的终点
这题我感觉不全是个算法题了,还是个数学题哈哈。
先摆出论断:
- 快慢指针从链表头开始走,相遇的那点,记为 M;
- 再用 2 个指针,一个从头开始走,一个从 M 开始走,相遇点即为 cycle 的终点。
咱们先看形象进去的图:
假如快慢指针在 M 点第一次相遇,
这里咱们设 3 个变量来示意这个链表里的几个重要长度:
- X:从链表头到环的终点的长度;
- Y:从环的终点到 M 点的长度;
- Z:从 M 点到环的终点的长度。
留神:因为环是有方向的,所以 Y 并不是 Z。
那其实咱们惟一晓得的关系就是:快慢指针在 M 点第一次相遇。这也是咱们最后假如的关系。
而快慢指针有一个永远不变的真谛:快指针走的长度永远是慢指针走的长度的 2 倍。
相遇时快慢指针别离走了多少的长度呢?
- 快指针:X+ Y + 假如走了 k 圈
- 慢指针:X + Y
那么咱们就能够用这个 2 倍的关系,列出下列等式:
2 * (X + Y) = X + Y + kL
所以 X + Y = kL
而咱们留神到:Y + Z = L,那么就能得出 X = Z。
所以当两个指针,一个从头开始走,一个从 M 点开始走时,相遇那点就是环的终点,证毕。
来看下代码吧:
public class Solution {public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode x = head;
ListNode y = slow;
while(x != y) {
x = x.next;
y = y.next;
}
return x;
}
}
return null;
}
}
这题还有个利用,就是找一个特定数组里反复的数字,这里就不开展了,大家感兴趣的去做一下吧~
接下来咱们聊聊 dummy node 这个技巧。
Dummy node
Dummy 的中文是“假”的意思,dummy node 大略能够翻译成虚构节点?有更纯粹的说法的话还请大家在评论区通知我呀~
一般来说,dummy node 的用法是在链表的实在 head 的后面加一个指向这个 head 的节点,目标是为了不便操作 head。
对于链表来说,head 是一个链表的灵魂,因为无论是查问还是其余的操作都须要从头开始,俗话说擒贼先擒王嘛,抓住了一个链表的头,就抓住了整个链表。
所以当须要对现有链表的头进行改变时,或者不确定头部节点是哪个,咱们能够事后加一个 dummyHead,这样就能够灵活处理链表中的残余局部,最初返回时去掉这个“假头”就好了。
很多时候 dummy node 不是必须,然而用了会很不便,缩小 corner case 的探讨,所以还是十分举荐应用的。
光说不练假把式,咱们间接来看题~
例 4:合并两个排好序的链表
这题有很多种解法,比方最直观的就是用两个指针,而后比拟大小,把小的接到最终的后果下来。
然而有点麻烦的是,最初的后果不晓得到底谁是头啊,是哪个链表的头作为了最终后果的头呢?
这种状况就非常适合用 dummy node。
先用一个虚构的头在这撑着,把整个链表结构好之后,再把这个假的剔除。
来看代码~
class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode dummy = new ListNode(0);
ListNode ptr = dummy;
while (l1 != null && l2 != null) { if (l1.val < l2.val) {
ptr.next = l1;
l1 = l1.next;
} else {
ptr.next = l2;
l2 = l2.next;
}
ptr = ptr.next;
}
if (l1 == null) {
ptr.next = l2;
} else {
ptr.next = l1;
}
return dummy.next;
}
}
这题也有升级版,就是合并 k 个排好序的链表。实质上也是一样的,只不过须要重写一下比拟器就好了。
例 5:删除节点
这道题的意思是删除链表中某个特定值的节点,可能有一个可能有多个,可能在头可能在尾。
如果要删除的节点在头的时候,新链表的头就不确定了,也有可能是个空的。。此时就很适宜用 dummy node 来做,躲避掉这些 corner case 的探讨。
那这题的思路就是:用 2 个指针
- prev:指向以后新链表的尾巴
- curr:指向以后正在遍历的 ListNode
如果 curr == 目标值,那就间接移到下一个;
如果 curr != 目标值,那就把 prev 指向它,接上。
这题须要留神的是,最初肯定要把 prev.next 指向 null,否则如果原链表的尾巴是目标值的话,还是去不掉。
代码如下:
class Solution {public ListNode removeElements(ListNode head, int val) { ListNode dummy = new ListNode(0);
ListNode prev = dummy;
ListNode curr = head;
while(curr != null) { if (curr.val != val) {
prev.next = curr;
prev = prev.next;
}
curr = curr.next;
}
prev.next = null;
return dummy.next;
}
}
好了,以上就是本文的所有内容了,如果这篇文章对你有帮忙,欢送分享给你身边的敌人,也给齐姐点个「在看」,你们的反对是我创作的最大能源!
悄悄话
最近开明了视频号,精力扩散了许多,没想到录个 1 分钟的短视频也能这么多事。。
然而 公众号照常分享技术干货和《齐姐聊大厂》系列,还请大家持续关注反对呀,为了保障内容的优质在线,可能筹备工夫有点长,多谢大家的急躁期待~~如果想我了就来视频号里找我玩~
最初,如果你对小齐的文章或者视频有什么想法或倡议,欢送留言或者私信与我多多交换,我是小齐,终生学习者,咱们下期见!