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

简介: 一.问题来源   昨晚看微博,发现于梁斌penny,他在说现在的面试制度考不出来真功夫,也就是基本功,面试题千篇一律的算法,看过会,不看就不会。期间提到了快慢指针求中位数。   查资料时我发现,这其实是计算机系统原理里的知识点。

一.问题来源

  昨晚看微博,发现于梁斌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开始),看分解如下表。

1 3 5 2 4 1
1 2 3 4 5 1

 

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点尽可能靠近源点,也就是说相遇尽可能早,这样复杂度就低了)?看下图,自己研究吧,笔者未做详细探索。

 

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

目录
相关文章
|
1月前
|
存储 安全 C++
C++中的引用和指针:区别与应用
引用和指针在C++中都有其独特的优势和应用场景。引用更适合简洁、安全的代码,而指针提供了更大的灵活性和动态内存管理的能力。在实际编程中,根据需求选择适当的类型,能够编写出高效、可维护的代码。理解并正确使用这两种类型,是掌握C++编程的关键一步。
26 1
|
15天前
|
存储 C语言
C语言数组指针详解与应用
C语言数组指针详解与应用
16 0
|
1月前
|
C++ 存储 Java
C++ 引用和指针:内存地址、创建方法及应用解析
'markdown'C++ 中的引用是现有变量的别名,用 `&` 创建。例如:`string &meal = food;`。指针通过 `&` 获取变量内存地址,用 `*` 创建。指针变量存储地址,如 `string *ptr = &food;`。引用不可为空且不可变,指针可为空且可变,适用于动态内存和复杂数据结构。两者在函数参数传递和效率提升方面各有优势。 ```
|
2月前
|
C++
多重指针:深入解析、应用与示例
多重指针:深入解析、应用与示例
|
2月前
|
存储 算法 C++
函数的指针:理解与应用
函数的指针:理解与应用
11 1
|
2月前
|
存储 程序员 C语言
C语言中的函数指针及其应用技术
C语言中的函数指针及其应用技术
26 2
|
29天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
2月前
|
C语言
文件类型指针及其在编程中的应用
文件类型指针及其在编程中的应用
24 0
|
2月前
|
存储 程序员 C语言
C语言指针变量的深入解析与应用
C语言指针变量的深入解析与应用
27 0
|
2月前
|
存储 算法 C语言
C语言指针与二维数组在函数参数传递和动态内存管理中的应用
C语言指针与二维数组在函数参数传递和动态内存管理中的应用
23 0