链表链表是数据结构中非常基础但非常可测试的线性结构。链表的操作比较简单，但是很适合面试官复习和写作。代码的能力、cornercase的处理、指针的应用，很容易造成NPE（nullpointerexception）。基于以上原因，链表在面试中非常重要。说到链表，就不得不提到数组。它们可以说是数据结构的基础。它们之间的主要区别在于：数组在物理内存中必须是连续的。链表在物理内存中不需要连续。它们通过指针连接。数组最好的特性是它可以被随机访问。使用索引，可以在O(1)时间内访问元素。因为链表不是连续的，不可能在O(1)时间内定位到任意一个元素的位置，所以只能从头开始遍历。这就造成了它们之间增删改查效率的差异。另外，链表本身的结构与数组完全不同。LinkedList由ListNode实现：classListNode{intvalue;ListNodenext;}结构上是这样的：这是一个单向链表，另一个链表是双向链表，也就是还有一个previous指针指向当前节点的上一个节点：classListNode{intvalue;ListNodeext;ListNodeprev;}其实链表相关的题没有什么难的，套路就那么几个。其中考的最多也是最基础的一道题就是反转链表。听说微软可以用这道题刷掉一半的考生，通过这两种方法得到bugfree还是不容易的。文章之前写过，点此直达评测。今天我们就来说说链表中最重要的两个技巧：双指针法和虚节点。相信看完这篇文章，你可以处理大部分与链表相关的问题。双指针法双指针法在很多数据结构和题型中都用到了，其中速度指针在链表中用的最多。顾名思义，两个指针中的一个移动快，另一个移动慢。这样做的好处是，以不同的速度遍历链表，方便找到目标位置。常见问题，如寻找链表的中点，或判断链表是否有环。例1：求中点题，给一个链表，然后求它的中点。如果是奇数，就好办了。如果是偶数，则问题需要返回到第二个。例如：1->2->3->4->5->NULL，需要返回3这个ListNode；1->2->3->4->5->6->NULL，需要返回4这个ListNode。但实际上，如果真要设计这样的API，我更倾向于选择返回偶数中的第一个中点。为什么？算法题是工业生产中一些问题的抽象。比如我们找中点的目的是断开链表，那么如果返回3，我就可以断开3和4；但是如果返回4，如何断开单向链表中4之前的地方呢？请再做一次。解题方法1.这道题最直观的解法就是先求链表的长度，然后走一半长度得到中点。classSolution{publicListNodemiddleNode(ListNodehead){if(head==null){returnnull;}intlen=0;ListNodecurrent=head;while(current!=null){len++;currentcurrent=current.next;}len/=2;ListNoderesult=head;while(len>0){resultresult=result.next;len--;}returnresult;}}方法二、快慢指针我们用两个指针一起遍历链表，每次快指针走2步，而慢指针走1步，这样当快指针到达终点时，慢指针应该刚好在链表的中点。classSolution{publicListNodemiddleNode(ListNodehead){ListNodeslow=head;ListNodefast=head;while(fast!=null&&fast.next!=null){slowslow=slow.next;fastfast=fast.next.next;}returnslow;}}这两个哪个方法比较好？网上很多人说方法一把链表遍历两次，方法二只遍历一次。但其实方法二是用两个指针来遍历，所以这两个方法遍历的次数是一样的。它们最大的区别是：第一种方法是离线算法，第二种方法是在线算法。公司的数据量是连续的。比如电商系统一直有客户下单，社交软件的好友数量一直在增加。这些是数据流，我们无法计算数据流的长度。然后在线算法可以随时给出当前结果。不用说，全部数据录入之后，其实并不能完成记录。.这就是在线算法比离线算法有很大优势的地方。更多解释可以参考stackoverflow上的这个问题，链接在文末。例2：判断单链表是否有环思路：从头开始连同快慢指针，每次快指针走2步，慢指针只走1步。如果有环，那么两个指针肯定会相遇。这道题就是典型的龟兔赛跑，或者在操场上跑圈的时候，跑得快的同学总是跑圈慢。publicclassSolution{publicbooleanhasCycle(ListNodehead){ListNodeslow=head;ListNodefast=head;while(fast!=null&&fast.next!=null){slowslow=slow.next;fastfast=fast.next.next;if(slow==fast){returntrue;}}returnfalse;}}这道题有升级版，要求回到圆环起点。例3：回到链表环的起点感觉这道题不完全是算法题，而是一道数学题哈哈。先得出结论：快慢指针从链表头部开始，相交点记为M；然后用2个指针，一个从头开始，一个从M开始，交点就是循环的起点。先看抽象图：假设快慢指针第一次相遇在M点，这里设置3个变量代表这个链表中几个重要的长度：X：距离链表头部的长度到环的起点；Y：环的起点到M点的长度；Z：M点到圆环起点的长度。注意：Y不是Z，因为环是定向的。事实上，我们唯一知道的关系就是快指针和慢指针在M点第一次相遇。这也是我们最初假设的关系。而快慢指针有一个永恒的真理：快指针的长度永远是慢指针长度的两倍。快指针和慢指针相遇时分别走了多长时间？快指针：X+Y+假设慢指针的k圈：X+Y那么我们可以利用这个2次关系列出如下等式：2*(X+Y)=X+Y+kL所以X+Y=kL和我们记：Y+Z=L，则得到X=Z。所以当两个指针，一个从头开始，一个从M点开始，它们相交的点就是环的起点，证明完成了。让我们看一下代码：(慢==快){ListNodex=head;ListNodey=slow;while(x!=y){xx=x.next;yy=y.next;}returnx;}}returnnull;}}这道题还有一个应用，就是找特定数组中重复的数字，这里就不展开了。有兴趣的就动手吧~接下来说说dummynode的技巧。DummynodeDummy中文意思是“假”。也许虚拟节点可以翻译成虚拟节点？如果大家有更真实的说法，请在评论区告诉我~一般来说dummynode的用法就是在链表真正的头部前面增加一个指向这个头部的节点，目的是为了方便头的操作。对于链表来说，表头是链表的灵魂，因为无论是查询还是其他操作，都需要从头开始。俗话说，擒贼先擒王。如果你抓住一个链表的头，你就会抓住整个链表。所以当我们需要改变现有链表的头部，或者不确定头部节点是哪个时，可以预先添加一个dummyHead，这样我们就可以灵活处理链表的其余部分，最后去掉“dummy头”返回时。好吧。很多情况下，dummynode不是必须的，但是使用起来很方便，也可以减少对cornercase的讨论，所以还是很推荐的。就说说造假的技巧吧，直接看题吧~例4：合并两个排序好的链表。这个问题有很多解法。到最后的结果。但是有点麻烦的是最后的结果不知道谁是头。哪个链表头是最终结果的头？这种情况非常适合虚拟节点。这里先用一个虚拟头来支撑，整个链表构造完成后，去掉假头。看代码~classSolution{publicListNodemergeTwoLists(ListNode1,ListNode2){if(l1==null){returnl2;}if(l2==null){returnl1;}ListNodummy=newListNode(0);ListNodeptr=dummy;while(l1!=null&&l2!=null){if(l1.val
