网站建设公司财务预算,永久免费虚拟空间,苏州网上挂号,怎么判断网站好坏链表链表是数据结构里一个很基础但是又很爱考的线性结构#xff0c;链表的操作相对来说比较简单#xff0c;但是非常适合考察面试者写代码的能力#xff0c;以及对 corner case 的处理#xff0c;还有指针的应用很容易引起 NPE (null pointer exception)。综合以上原因链表的操作相对来说比较简单但是非常适合考察面试者写代码的能力以及对 corner case 的处理还有指针的应用很容易引起 NPE (null pointer exception)。综合以上原因链表在面试中很重要。提到链表就不得不提数组它和数组可以说是数据结构的基础那么它们最主要的区别在于数组在物理内存上必须是连续的链表在物理内存上不需要连续通过指针连接所以数组最好的性质就是可以随机访问 random access有了 index可以 O(1) 的时间访问到元素。而链表因为不连续所以无法 O(1) 的时间定位任意一个元素的位置那么就只能从头开始遍历。这就造成了它们之间增删改查上效率的不同。除此之外链表本身的结构与数组也是完全不同的。LinkedList 是由 ListNode 来实现的class ListNode {int value;ListNode next;
}
结构上长这样这是单向链表那还有的链表是双向链表也就是还有一个 previous pointer 指向当前 node 的前一个 nodeclass ListNode {int value;ListNode next;ListNode prev;
}
其实链表相关的题目没有很难的套路也就这么几个其中最常考最基础的题目是反转链表听说微软可以用这道题电面刷掉一半的 candidate两种方法一遍 bug free 还是不容易的。文章之前已经写过了点击这里直达复习。今天我们来说链表中最主要的 2 个技巧双指针法和 dummy node相信看完本文后链表相关的绝大多数题目你都能搞定啦。双指针法双指针法在很多数据结构和题型中都有应用在链表中用的最多的还是快慢指针。顾名思义两个指针一个走得快一个走得慢这样的好处就是以不同的速度遍历链表方便找到目标位置。常见的问题比如找一个链表的中点或者判断一个链表是否有环。例 1找中点这题就是给一个链表然后找到它的中点如果是奇数个很好办如果是偶数个题目要求返回第二个。比如1 - 2 - 3 - 4 - 5 - NULL需要返回 3 这个 ListNode1 - 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 的这个问题[1]链接在文末。例 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 nodeDummy 的中文是“假”的意思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;}
}
好了以上就是本文的所有内容了如果这篇文章对你有帮助欢迎分享给你身边的朋友也给我点个「在看」你们的支持是我创作的最大动力
往期推荐
链表反转的两种实现方法后一种击败了100%的用户漫画如何找到链表的倒数第n个结点算法图解如何用两个栈实现一个队列关注我每天陪你进步一点点
