关于快慢指针的若干应用详解

客官°小女子只卖身不卖艺 2022-06-07 03:27 142阅读 0赞

# [关于快慢指针的若干应用详解][Link 1] #

# 一.问题来源 #

昨晚看微博，发现于梁斌penny，他在说现在的面试制度考不出来真功夫，也就是基本功，面试题千篇一律的算法，看过会，不看就不会。期间提到了快慢指针求中位数。

查资料时我发现，这其实是计算机系统原理里的知识点。

# 二.快慢指针概念 #

快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2，慢指针每次向前移动1次。

# 三.快慢指针的应用 #

## 3.1 判断单链表是否为循环链表 ##

对于初学者来说，要解决这个问题，最可能采取的方法就是使用两个循环。当外层循环步进一个节点时，内层循环就遍历外层循环节点之后的所有节点，然后比较内外循环的两个节点。若有节点地址相等，则表明该单链表有循环，反之则不存在循环。这种方法无疑效率比较低。

今天给大家介绍一个经典的方法，通过快慢指针来检查单链表是否存在循环。其思路很简单，大家可以想一下上体育课长跑的情景。当同学们绕着操场跑步的时候，速度快的同学会遥遥领先，最后甚至会超越其它同学一圈乃至n圈——这是绕圈跑。那么如果不是绕圈跑呢？速度快的同学则会一直领先直到终点，不会再次碰到后面的速度慢同学——不考虑地球是圆的这种情况。

快慢指针的设计思想也是这样。快指针每次步进多个节点——这个视情况而定，慢指针每次只步进一个节点。那么如果该链表存在循环的话，快指针一定会再次碰到慢指针，反之则不存在循环。

让快慢指针从链表头开始遍历，快指针向前移动两个位置，慢指针向前移动一个位置;如果快指针到达NULL，说明链表以NULL为结尾，不是循环链表。如果 快指针追上慢指针，则表示出现了循环。

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> 
    <div>
      14 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>int</code> 
      <code> isExitsLoop(LinkList L) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>LinkList fast, slow;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>fast = slow = L;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(fast &amp;&amp; fast-&gt;next)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>slow = slow-&gt;next;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>fast = fast-&gt;next-&gt;next;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(slow == fast)</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>{ </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>break</code> 
      <code>;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>((fast == NULL) || (fast-&gt;next == NULL));</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

注：不一定直接是一个环，可能说先共同走一段路，在尾部形成环。如果是第一种情况(长度为5，从1开始)，看分解如下表。

![061332526654646.png][]

## 3.2 在有序链表中寻找中位数 ##

该方法在不借助计数器变量实现寻找中位数的功能。原理是：快指针的移动速度是慢指针移动速度的2倍，因此当快指针到达链表尾时，慢指针到达中点。程序还要考虑链表结点个数的奇偶数因素，当快指针移动x次后到达表尾（1+2x），说明链表有奇数个结点，直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点，说明链表结点个数是偶数，这时可以根据“规则”返回上中位数或下中位数或（上中位数+下中位数）的一半。

## 3.3 如果链表为存在环，如果找到环的入口点？ ##

有一个单链表，其中可能有一个环，也就是某个节点的next指向的是链表中在它之前的节点，这样在链表的尾部形成一环。  
　　那么问题来了，如何判断一个链表是不是这类链表？如果链表为存在环，如果找到环的入口点？　　当fast若与slow相遇时，slow肯定没有走遍历完链表(不是一整个环，有开头部分，如上图)或者恰好遍历一圈(未做验证，看我的表格例子，在1处相遇)。*于是我们从链表头、与相遇点分别设一个指针，每次各走一步，两个指针必定相遇，且相遇第一点为环入口点(慢指针走了n步，第一次相遇在c点，对慢指针来说n=s+p，也就是说如果慢指针从c点再走n步，又会到c点，那么顺时针的CB距离是n-p=s，但是我们不知道s是几，那么当快指针此时在A点一步一步走，当快慢指针相遇时，相遇点恰好是圆环七点B(AB=CB=s))。*

<table> 
 <tbody> 
  <tr> 
   <td> 
    <div>
      1 
    </div> 
    <div>
      2 
    </div> 
    <div>
      3 
    </div> 
    <div>
      4 
    </div> 
    <div>
      5 
    </div> 
    <div>
      6 
    </div> 
    <div>
      7 
    </div> 
    <div>
      8 
    </div> 
    <div>
      9 
    </div> 
    <div>
      10 
    </div> 
    <div>
      11 
    </div> 
    <div>
      12 
    </div> 
    <div>
      13 
    </div> 
    <div>
      14 
    </div> 
    <div>
      15 
    </div> 
    <div>
      16 
    </div> 
    <div>
      17 
    </div> 
    <div>
      18 
    </div> 
    <div>
      19 
    </div> 
    <div>
      20 
    </div> </td> 
   <td> 
    <div> 
     <div> 
      <code>node* findLoopPort(node *head) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>node *fast, *slow;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>fast = slow = head;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(fast &amp;&amp; fast-&gt;next) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>slow = slow-&gt;next;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>fast = fast-&gt;next-&gt;next;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>(slow == fast) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>break</code> 
      <code>;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>if</code> 
      <code>((fast == NULL) || (fast-&gt;next == NULL)) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>NULL;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>slow = head;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>while</code> 
      <code>(slow != fast) { </code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>slow = slow-&gt;next;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>fast = fast-&gt;next;</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>}</code> 
     </div> 
     <div> 
      <code>&nbsp;&nbsp;&nbsp;&nbsp;</code> 
      <code>return</code> 
      <code>slow;</code> 
     </div> 
     <div> 
      <code>}</code> 
     </div> 
    </div> </td> 
  </tr> 
 </tbody> 
</table>

## 3.4 扩展问题 ##

判断两个单链表是否相交，如果相交，给出相交的第一个点（两个链表都不存在环）。

比较好的方法有两个：

1.将其中一个链表首尾相连，检测另外一个链表是否存在环，如果存在，则两个链表相交，而检测出来的依赖环入口即为相交的第一个点。  
　　2.如果两个链表相交，那个两个链表从相交点到链表结束都是相同的节点，我们可以先遍历一个链表，直到尾部，再遍历另外一个链表，如果也可以走到同样的结尾点，则两个链表相交。  
这时我们记下两个链表length，再遍历一次，长链表节点先出发前进(lengthMax-lengthMin)步，之后两个链表同时前进，每次一步，相遇的第一点即为两个链表相交的第一个点。

# 四.参考文献及结束语 #

## 4.1 问题1 ##

相差多少？才能保证相遇？如果从物理学的角度理解(s-t曲线)，肯定相遇，那么问题是如何尽快相遇(也就是快慢指针相差几倍才能使A点尽可能靠近源点，也就是说相遇尽可能早，这样复杂度就低了)？看下图，自己研究吧，笔者未做详细探索。

![061337411963731.png][]

## 4.2 问题2 ##

s=t，s=2t和s=3t，s=6t的效果一样吗？

## 4.3 感想 ##

指针可以相差倍数，那也可以相差固定位数啦？比如求链表的倒数第n位.

## 4.4 参考文献 ##

http://anyhu.blog.sohu.com/184515249.html  
　　http://www.nowamagic.net/librarys/veda/detail/1842

[Link 1]: http://www.cnblogs.com/hxsyl/p/4395794.html
[061332526654646.png]: /images/20220607/2d18b2c61eab465a8b14817fc475b19e.png
[061337411963731.png]: /images/20220607/ed4dcb2c1dd8453596c60a04dc57a954.png