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

一时失言乱红尘 2022-03-31 15:24 240阅读 0赞

# 一.问题来源 #

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

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

# 二.快慢指针概念 #

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

# 三.快慢指针的应用 #

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

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

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

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

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

int isExitsLoop(LinkList L) {
        LinkList fast, slow;
        fast = slow = L;
    	while (fast && fast->next)
        {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast)
            {
                break;
            }
        }
        return ((fast == NULL) || (fast->next == NULL));
    }

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

![061332526654646.png][]

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

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

while (fast&&slow) 
    { 
    　　if (fast->next==NULL) 
    　　    return slow ->data; 
    　　else if (fast->next!= NULL && fast->next->next== NULL) 
    　　    return (slow ->data + slow ->next->data)/2; 
    　　else 
    　　{ 
    　　    fast= fast->next; 
    　    　fast= fast->next; 
    　　    slow = slow ->next; 
    　　} 
    　}

## 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))。*

node* findLoopPort(node *head) {
        node *fast, *slow;
        fast = slow = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                break;
            }
        }
        if ((fast == NULL) || (fast->next == NULL)) {
            return NULL;
        }
        slow = head;
        while (slow != fast) {
            slow = slow->next;
            fast = fast->next;
        }
        return slow;
    }

## 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

[061332526654646.png]: /images/20220331/aa4bbb08dd144b6e9de4ee5607784730.png
[061337411963731.png]: /images/20220331/2a04148b4cb34dba9a3d629c03a31b04.png