快慢指针也是面试中的一个常考知识点,主要是链表的问题中应用较多。
1. 判断链表是否存在环
设置两个指针(fast, slow),初始值都指向头,slow每次前进一步,fast每次前进二步,如果链表存在环,则fast必定先进入环,而slow后进入环,两个指针必定相遇。(当然,fast先行头到尾部为NULL,则为无环链表)程序如下:
01 |
int isExitsLoop(LinkList L) {
|
04 |
while (fast && fast->next)
|
07 |
fast = fast->next->next; |
13 |
return ((fast == NULL) || (fast->next == NULL));
|
找到环的入口点
当fast若与slow相遇时,slow肯定没有走遍历完链表,而fast已经在环内循环了n圈(1<=n)。假设slow走了s步,则fast走了2s步(fast步数还等于s 加上在环上多转的n圈),设环长为r,则:
设整个链表长L,入口环与相遇点距离为x,起点到环入口点的距离为a。
2 |
a + x = (n – 1)r +r = (n-1)r + L - a |
3 |
a = (n-1)r + (L – a – x) |
(L – a – x)为相遇点到环入口点的距离,由此可知,从链表头到环入口点等于(n-1)循环内环+相遇点到环入口点,于是我们从链表头、与相遇点分别设一个指针,每次各走一步,两个指针必定相遇,且相遇第一点为环入口点。程序描述如下:
01 |
node* findLoopPort(node *head) { |
04 |
while (fast && fast->next) {
|
06 |
fast = fast->next->next; |
11 |
if ((fast == NULL) || (fast->next == NULL)) {
|
15 |
while (slow != fast) {
|
如何快速找出未知长度单链表的中间节点?
普通方法:先遍历一遍单链表确定其长度L后,再从头节点出发循环L/2次即可查找到单链表的中间节点。该问题如果采用普通的方法虽然简单,但是查找效率太低。
快慢指针: 设置两个指针*fast、*slow都指向单链表的头节点,其中*fast的移动速度是*slow的2倍,当*fast指向末尾节点的时候,slow正好就在中间了,可以大大提高查找的效率。
当然,此时算法 还要考虑链表结点个数的奇偶数因素,当快指针移动x次后到达表尾(1+2x),说明链表有奇数个结点,直接返回慢指针指向的数据即可。如果快指针是倒数第二个结点,说明链表结点个数是偶数,这时 可以 实际情况 返回上中位数或下中位数或(上中位数+下中位数)的一半。
这个应用实际在前面讲到的对链表进行排序有用过。
参考 :http://www.acmerblog.com/fast-slow-pointer-5382.html
分享到:
相关推荐
快慢指针中的快慢指的是移动的步长,即每次向前移动速度的快慢。例如可以让快指针每次沿链表向前移动2,慢指针每次向前移动1次。判断单链表是否为循环链表:让快慢指针从链表头开始遍历,快指针向前移动两个位置,慢...
给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了
已知head为单链表的表头指针,链表中存储的都是整形数据,实现下列运算的递归算法: (1)求链表中的最大值。 (2)求链表中的结点个数。 (3)求所有整数的平均值。
详细介绍,C语言中用指针处理链表。 以及对链表的建立和插入,删除等等操作。
关于在链表中实现插入法排序 相对于数据结构为数组的插入排序方法,现在要解决的是如何实现链表中的插入排序。数组的存储方式是顺序存储,而链表的存储方式是链式存储。所以,要实现针对链表的插入排序法,其关键是...
头插法创建链表 打印输出链表内容 利用快慢指针法找出链表中间元素 链表内容为奇数个时,打印中间值 链表内容为偶数个时,打印中间两个值
示例 1:输入: 1->2示例 2:输入: 1->2->2->1* Definition for singly-linked list.//率先进行快慢指针找到
教程描述:C++指针和链表在项目开发中的实战应用教程由传智播客录制,主要讲解链表知识体系搭建相关问题、链表知识领域技术推演、通用链表的设计与实现集成测试、通用链表的设计与实现_api实现与调试、链表模板类...
简单的学习指针和链表,通过尾插法建立链表,实现对数据的查找、插入和删除。
C语言实现:头插法创建链表,打印输出链表内容,利用快慢指针法找出链表中间元素,链表内容为奇数个时,打印中间值, 链表内容为偶数个时,打印中间两个值
指针链表的演示,C++ builder6 调试通过。
主要介绍了面试题快慢链表和快慢指针的相关资料,需要的朋友可以参考下
C语言 指针与链表 实验报告 堆栈和队列的各种操作
数据结构算法\第3章 链表及其应用数据结构算法\第3章 链表及其应用数据结构算法\第3章 链表及其应用
设计算法以判断一个带头结点的单循环链表是否满足...若成立,返回TRUE,否则返回FALSE,任务利用递增有序地单循环链表表示集合,分别求两个链表表示的集合的交、并集所构成的链表,设计算法以构造带头结点的双循环链表。
list.h在应用层应用
而快慢指针一般在链表中运用较多,在反转链表和定位链表节点及链表成环等逻辑中运用比较广泛。 141. 环形链表 逻辑非常简单,只要是环形的链表,那么快慢指针早晚会遇到。 值得注意的一点是,用try…except…来进行...
实现对学生信息管理系统,其中包括学生信息的添加、删除、查找、学生信息表的合并等
文章主要介绍在c语言中用结构体和指针构造链表的方法,感兴趣的朋友可以看看。