使用双指针解决链表题（好好好）

发癫：  

  你知道吗，力扣倒着读就是库里（扣力）哦！

  啦啦啦 啦啦 啦啦啦，CodeLeet,  CodeLeet,  CodeLeet CodeLeet !

正文：

  ok，废话少说，这是一篇初出茅庐的小白被链表题整疯后对双指针解决链表题的见解。

  双指针,即使用两个指针去解决问题。能用两个指针解决的问题通常用一个指针也能解决，但是双指针相比于单指针，在时间复杂度和空间复杂度方面都占优势。

（来源：LeetCode）

  像这一题，使用单指针并重新开辟一个链表即使是一个小白（我第一次就是这样写的）也可以很轻松地解答出来；使用双指针，假设为 p1, p2 ：p2 用于判断“值”是否符合，且保证 p2 一直是 p1 的下一位，用来决定 p1 是顺序移动还是跳过（还可以设定一个哨兵位来辅助）。可以将空间复杂度降为O(1)，虽然不是什么很强的优化，但是起码看起来比用单指针厉害呀！(滑稽)

  什么？！双指针太麻烦，🐕都不用？！不不不，单指针的上限可远不如双指针，接下来登场的是将双指针优势发挥到极致的——快慢指针：

（来源：LeetCode）

  这一题使用单指针同样能解决，就是先遍历一遍链表获取链表长度，然后再遍历一次(只遍历一遍);如果使用快慢指针，快指针一次走两步，慢指针一次走一步，当快指针到尾节点时，慢指针刚好到达中间节点，听懂掌声！！！

（来源：LeetCode）

  刚才那题单链表还有发挥空间，但这一题用单链表一走就是一辈子了。

  那么用快慢指针是个什么样的解法呢？这题其实还是比较吃数学思维的：这道题要分两个部分来解决，一是判断是否有环，二是找进入环的节点。

  一、判断:

  依旧是快指针走两步，慢指针走一步，当它们两个能够相遇，就说明这个链表中有环。

  如果链表没有环快慢指针当然是不可能相遇的，关于如何证明有环必定相遇，不妨把两个指针入环之后的运动当作追击运动。当慢指针入环，快指针必定在环中已经运动一段时间，假设此时快指针追击慢指针所需要经过的距离为N,因为快指针走两步，慢指针才走一步，那么每次它们的距离缩短一个节点，当运动N次时，快指针追上慢指针。

  二、找入环节点:

  这里同样需要两个指针，一个指针从原链表的头节点开始每次一步，一个指针从前面快慢指针相遇的节点开始同样每次一步，当这次的两个指针相遇，相遇的节点即为入环节点。

  这一步的证明就比较麻烦了。

  首先需要清楚，当慢指针和快指针相遇时，慢指针必然不可能完全绕环运动过一周。因为假设环的长度为 C ,当慢指针运动 C 的一半时,快指针至少已经绕过环一周(即一个完整的 C ),当慢指针开始完成剩下的一半路程时，无论快指针在哪，都一定可以在慢指针完成一圈之前追上它。

  然后，不妨假设从头节点到入环节点的距离为 A ,从入环节点按顺序抵达相遇节点的距离为 B ，慢指针走过的总路程则为 A + B ,快指针可能绕环 n 周，它走过的路程为 A + B + n * C 。根据它们之间的路程关系，有：

  即 A  = n * C - B，左边是从头节点开始运动的指针走到入环节点所要走的路程，右边可以看作从相遇节点开始的指针绕了环 n 圈之后再次回到入环节点的路程。

   以上的快慢指针都是动态的，还是很吃脑子的的呀！最后再讲一个静态的，比较简单，缓一缓。

  如果能写出前面的题目，这一题简直就是小儿科啦。

  同样使用到两个指针，但是把这两个指针分别叫做前指针和后指针更好理解。一开始两个指针都指向头节点，然后根据 k 的不同,让前指针先运动，k = 1 运动一步，k = 2 运动两步，以此类推。之后前指针和后指针同时运动，当前指针为空，后指针指向的节点就是要找的节点。

总结：

  最后总结一下：时间复杂度方面， 由于比单指针多一个指针，所以在需要遍历链表时，双指针的比单指针更具优势，甚至可以达到 一加一大于二 的效果。空间复杂度更不用说，能把O(n)降为O(1)，是一个巨大的提升。双指针还能让链表的拼接、分割、合并等操作逻辑更清晰，甚至可以在一次遍历中同时完成 “遍历、判断、修改” 等多步操作，避免重复遍历带来的性能损耗。

  双指针的讲解到此结束。