-
有环链表监测方法
2019-10-06 22:27:27文章目录有环链表检测链表是否有环的两种方法 有环链表 检测链表是否有环的两种方法 第一种快慢指针法 快慢指针法,每次走一步,另外一个指针每次走两步,或者更多,当两个指针能够指向同一个位置的时候,说明...有环链表
代码地址数据结构代码仓库
循环链表示例图
+-------------------------------------------------+ v | +---+ +---+ +---+ +---+ +---+ +---+ +---+ | 1 | --> | 2 | --> | 3 | --> | 4 | --> | 5 | --> | 6 | --> | 7 | +---+ +---+ +---+ +---+ +---+ +---+ +---+
检测链表是否有环的两种方法
第一种快慢指针法
快慢指针法,每次走一步,另外一个指针每次走两步,或者更多,当两个指针能够指向同一个位置的时候,说明链表中存在环。
// 利用快慢指针的方法 int HasLoop2(LinkList L) { LinkList p = L; LinkList q = L; while (p != NULL && q != NULL && q->next != NULL) { p = p->next; if (q->next != NULL) q = q->next->next; printf("p:%d, q:%d \n", p->data, q->data); if (p == q) return 1; } return 0; }
第二种比较步数法
一个指针每次向前走一步,走的次数为n,另一个指针每次从头开始向前走(最多走n步),当两个指针指向同一个位置的时候,但是第二个指针走的步数小于n(或者说不等于n),这时说明链表中存在环
// 比较步数的方法 int HasLoop1(LinkList L) { LinkList cur1 = L; // 定义结点 cur1 int pos1 = 0; // cur1 的步数 while(cur1) { // cur1 结点存在 LinkList cur2 = L; // 定义结点 cur2 int pos2 = 0; // cur2 的步数 while(cur2) { // cur2 结点不为空 if(cur2 == cur1) { // 当cur1与cur2到达相同结点时 if(pos1 == pos2) // 走过的步数一样 break; // 说明没有环 else // 否则 { printf("环的位置在第%d个结点处。\n\n", pos2); return 1; // 有环并返回1 } } cur2 = cur2->next; // 如果没发现环,继续下一个结点 pos2++; // cur2 步数自增 } cur1 = cur1->next; // cur1继续向后一个结点 pos1++; // cur1 步数自增 } return 0; }
#include <stdio.h> #include <stdlib.h> #include <time.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status;/* Status是函数的类型,其值是函数结果状态代码,如OK等 */ typedef int ElemType;/* ElemType类型根据实际情况而定,这里假设为int */ typedef struct Node { ElemType data; struct Node *next; }Node, *LinkList; /* 初始化带头结点的空链表 */ Status InitList(LinkList *L); /* 初始条件:顺序线性表L已存在。操作结果:返回L中数据元素个数 */ int ListLength(LinkList L); /* 随机产生n个元素的值,建立带表头结点的单链线性表L(头插法) */ void CreateListHead(LinkList *L, int n); /* 随机产生n个元素的值,建立带表头结点的单链线性表L(尾插法) */ void CreateListTail(LinkList *L, int n); // 利用快慢指针的方法 int HasLoop2(LinkList L); int HasLoop1(LinkList L); /* 初始化带头结点的空链表 */ Status InitList(LinkList *L) { *L = (LinkList)malloc(sizeof(Node)); /* 产生头结点,并使L指向此头结点 */ if(!(*L)) /* 存储分配失败 */ return ERROR; //< 初始化的首节点,指向为NULL的数据 (*L)->next=NULL; /* 指针域为空 */ return OK; } /* 初始条件:顺序线性表L已存在。操作结果:返回L中数据元素个数 */ int ListLength(LinkList L) { int i=0; LinkList p=L->next; /* p指向第一个结点 */ while(p) { i++; p=p->next; } return i; } /* 随机产生n个元素的值,建立带表头结点的单链线性表L(头插法) */ void CreateListHead(LinkList *L, int n) { LinkList p; int i; srand(time(0)); /* 初始化随机数种子 */ *L = (LinkList)malloc(sizeof(Node)); (*L)->next = NULL; /* 建立一个带头结点的单链表 */ for (i=0; i < n; i++) { p = (LinkList)malloc(sizeof(Node)); /* 生成新结点 */ p->data = rand()%100+1; /* 随机生成100以内的数字 */ p->next = (*L)->next; /* 新申请的节点放到老节点之前 */ (*L)->next = p; /* 插入到表头 */ } } /* ┌──────────────────────────┬───────────────┬─────────┐ │Interface │ Attribute │ Value │ ├──────────────────────────┼───────────────┼─────────┤ │rand(), rand_r(), srand() │ Thread safety │ MT-Safe │ └──────────────────────────┴───────────────┴─────────┘ */ /* 随机产生n个元素的值,建立带表头结点的单链线性表L(尾插法) */ void CreateListTail(LinkList *L, int n) { LinkList p,r; int i; srand(time(0)); /* 初始化随机数种子 */ *L = (LinkList)malloc(sizeof(Node)); /* L为整个线性表 */ r = *L; /* r为指向尾部的结点 */ for (i=0; i < n; i++) { p = (Node *)malloc(sizeof(Node)); /* 生成新结点 */ p->data = rand()%100+1; /* 随机生成100以内的数字 */ r->next=p; /* 将表尾终端结点的指针指向新结点 */ r = p; /* 将当前的新结点定义为表尾终端结点 */ } //< 生成循环链表,将尾节点指向第二个节点 (*L)->next->next r->next = (*L)->next->next; } // 比较步数的方法 int HasLoop1(LinkList L) { LinkList cur1 = L; // 定义结点 cur1 int pos1 = 0; // cur1 的步数 while(cur1) { // cur1 结点存在 LinkList cur2 = L; // 定义结点 cur2 int pos2 = 0; // cur2 的步数 while(cur2) { // cur2 结点不为空 if(cur2 == cur1) { // 当cur1与cur2到达相同结点时 if(pos1 == pos2) // 走过的步数一样 break; // 说明没有环 else // 否则 { printf("环的位置在第%d个结点处。\n\n", pos2); return 1; // 有环并返回1 } } cur2 = cur2->next; // 如果没发现环,继续下一个结点 pos2++; // cur2 步数自增 } cur1 = cur1->next; // cur1继续向后一个结点 pos1++; // cur1 步数自增 } return 0; } // 利用快慢指针的方法 int HasLoop2(LinkList L) { LinkList p = L; LinkList q = L; while (p != NULL && q != NULL && q->next != NULL) { p = p->next; if (q->next != NULL) q = q->next->next; printf("p:%d, q:%d \n", p->data, q->data); if (p == q) return 1; } return 0; } int main() { LinkList L; char opp; InitList(&L); printf("初始化L后:ListLength(L)=%d\n",ListLength(L)); printf("\n1.创建有环链表(尾插法) \n2.创建无环链表(头插法) \n3.判断链表是否有环 \n0.退出 \n\n请选择你的操作:\n"); while(opp != '0') { scanf("%c",&opp); switch(opp) { case '1': CreateListTail(&L, 7); printf("成功创建有环L(尾插法)\n"); printf("\n"); break; case '2': CreateListHead(&L, 7); printf("成功创建无环L(头插法)\n"); printf("\n"); break; case '3': printf("方法一: \n\n"); if( HasLoop1(L) ) { printf("结论:链表有环\n\n\n"); } else { printf("结论:链表无环\n\n\n"); } printf("方法二:\n\n"); if( HasLoop2(L) ) { printf("结论:链表有环\n\n\n"); } else { printf("结论:链表无环\n\n\n"); } printf("\n"); break; case '0': exit(0); } } }
代码地址数据结构代码仓库
-
[开心IT面试题] 检测两个非环链表是否有交点
2013-11-28 11:18:49题目:给定两个单链表(first, second),检测两个链表是否有交点,如果有返回第一个交点。 思路: 如果first==second,那么显然相交,直接返回first。 否则,分别从first,second开始遍历两个链表获得其长度len1与len2...题目:
给定两个非环单链表(first, second),检测两个链表是否有交点,如果有返回第一个交点。
思路:
如果first==second,那么显然相交,直接返回first。
否则,分别从first,second开始遍历两个链表获得其长度len1与len2。假设len1>len2,那么指针p1由first开始向后移动len1-len2步。
指针p2=second,下面p1、p2每次向后前进一步并比较是否相等,如果相等即返回该结点,否则说明两个链表没有交点。
代码:
Node *IsIntersect(Node *first, Node *second) { if(first == NULL || second == NULL) { return NULL; } Node *p1, *p2; p1 = first; p2 = second; int len1 = Length_LinkList(first); int len2 = Length_LinkList(second); if(len1 >= len2) { for(int i = 0; i < len1-len2; i++) { p1 = p1->next; } }else { for(int i = 0; i < len2-len1; i++) { p2 = p2->next; } } while(p1 != NULL && p2 != NULL) { if(p1 == p2) { return p1; } p1 = p1->next; p2 = p2->next; } return NULL; }
注:代码中所用到的计算单链表长度的Length_LinkList()函数请看“单链表基础”
扩展:考虑假设链表有环,应该怎么检测是否有交点?
-
leetcode1645环路检测(给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。有环链表的定义...
2020-08-05 17:19:56给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 ...给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。
示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。示例 2:
输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点。示例 3:
输入:head = [1], pos = -1
输出:no cycle
解释:链表中没有环。进阶:
你是否可以不用额外空间解决此题?思路图解:
代码实现:
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { //慢行指针slow ListNode slow = head; //快行指针fast ListNode fast = head; //在一个环上,看做谁追谁不是绝对的 while (true) { //若没有环,fast的最终指向会为空 if (fast == null || fast.next == null) { //无环直接返回空 return null; } //慢行指针步进1 slow = slow.next; //快行指针步进2 fast = fast.next.next; //相遇则暂停 if (slow == fast) { break; } } //p即为图解中指向原点O的指针 //图解中指向P的指针还是slow ListNode p = head; while (p != slow) { //两者步进都为1走向图解中的A点 p = p.next; slow = slow.next; } //循环退出时即同时到达A点 //返回图解A处的结点即为答案 return p; } }
-
给定一个有环链表,实现一个算法返回环路的开头结点
2017-04-17 20:25:39检测链表是否存在环路 有一种简单的做法叫FastRunner/SlowRunner法。FastRunner一次移动两步,而SlowRunner一次移动一步。这就好比两辆赛车绕着同一条赛道以不同的速度前进,最终必然会碰到一起。 聪明的读者可能会...检测链表是否存在环路
有一种简单的做法叫FastRunner/SlowRunner法。FastRunner一次移动两步,而SlowRunner一次移动一步。这就好比两辆赛车绕着同一条赛道以不同的速度前进,最终必然会碰到一起。
聪明的读者可能会问:FastRunner会不会刚好“越过”SlowRunner,而不发生碰撞呢?绝无可能。假设FastRunner真的越过了SlowRunner,且SlowRunner处于位置i,FastRunner位于位置i+1。那么,在前一步,SlowRunner就处于位置i-1,FastRunner处于位置((i+1)-2)或i-1。也就是说,两者碰在一起了。
什么时候碰在一起?
假定这个链表有一部分不存在环路,长度为k。
若运用上述算法,FastRunner和SlowRunner什么时候会碰在一起呢?
我们知道,SlowRunner每走p步,FastRunner就会走2p步。因此,当SlowRunner走了k步进入环路部分时,FastRunner已走了总共2k步,进入环路部分已有2k-k步或k步。由于k可能比环路长度大得多,实际上我们应该把它写作mod(k, LOOP_SIZE)步,并用K表示。
对于之后的每一步,FastRunner和SlowRunner之间不是走远一步就是更近一步,具体要看观察的角度。也就是说,因为两者处于圆圈中,当A以远离B的方向走出q步时,同时也是向B更近了q步。综上,我们得出以下几点:
(1)SlowRunner处于环路中的0步位置;
(2)FastRunner处于环路中的K步位置;
(3)SlowRunner落后于FastRunner,相距K步;
(4)FastRunner落后于SlowRunner,相距LOOP_SIZE-K步;
(5)每过一个单位时间,FastRunner就会更接近于SlowRunner一步。
那么,两个节点什么时候相遇?若FastRunner落后于SlowRunner,相距LOOP_SIZE-K步,并且每经过一个单位时间,FastRunner就走近SlowRunner一步,那么,两者将在LOOP_SIZE-K步之后相遇。此时,两者与环路起始处相距K步,我们将这个位置称为CollisionSpot。
如何找到环路起始处?
现在我们知道CollisionSpot与环路起始处相距K个节点。由于K=mod(k, LOOP_SIZE)(或者换句话说,k=K+M*LOOP_SIZE,其中M为任意整数),也可以说,CollisionSpot与环路起始处相距k个节点。例如,若有个环路长度为5个节点,有个节点N处于距离环路起始处2个节点的地方,我们也可以换个说法:这个节点处于距离环路起始处7个、12个甚至397个节点。
至此,CollisionSpot和LinkedListHead与环路起始处均相距k个节点。
现在,若用一个指针指向CollisionSpot,用另一个指针指向LinkedListHead,两者与LoopStart均相距k个节点。以同样的速度移动,这两个指针会再次碰在一起——这次是在k步之后,此时两个指针都指向LoopStart,然后只需返回该结点即可。
将全部整合在一起
总结一下,FastPointer的移动速度是SlowPointer的两倍。当SlowPointer走了k个节点进入环路时,FastRunner已进入链表环路k个节点。也就是说FastRunner和SlowRunner相距LOOP_SIZE-k个节点。
接下来,若SlowPointer每走一个节点,FastRunner就走两个节点,每走一次,两者的距离就会更近一个节点。因此,在走了LOOP_SIZE-k次后,它们就会碰在一起。这时两者距离环路起始处就有k个节点。
链表首部与环路起始处也相距k个节点。因此,若其中一个指针保持不变,另一个指针指向链表首部,则两个指针就会在环路起始处相会。
根据之前的4部分描述,就能直接导出下面的算法。
(1)创建两个指针:FastPointer和SlowPointer。
(2)SlowPointer每走一步,FastPointer就走两步。
(3)两者碰在一起时,将SlowPointer指向LinkedListHead,FastPointer保持不变。
(4)以相同速度移动SlowPointer和FastPointer,一次一步,然后返回新的碰撞处。
下面给出算法代码:
LinkedListNode findBegining(LinkedListNode head) { LinkedListNode slow = head; LinkedListNode fast = head; /*找出碰撞处,将处于链表中LOOP_SIZE-k步的位置*/ while(fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if(slow == fast) { // 碰撞 break; } } /*错误检查,没有碰撞处,也即没有回路*/ if(fast == null || fast.next == null) { return null; } /*将slow指向首部,fast指向碰撞处,两者距离环路 *起始处k步,若两者以相同速度移动,则必定会在环 *路起始处碰在一起*/ slow = head; while(slow != fast) { slow = slow.next; fast = fast.next; } /*至此两者均指向环路起始处*/ return fast; }
-
数据结构8:环链表返回环头结点
2020-10-15 12:30:43给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 题目解答 1.快慢指针只能检测是否有环,结果是... -
2.6给定一个有环链表,实现一个算法返回环路的开头结点。
2017-11-01 00:10:001、检测链路是否存在环路。通过FastRunner/SlowRunner法,FastRunner一次移动两步,SlowRunner一次移动一步。 2、当二者碰到之后,F继续走,S从头走。当他们再次碰头时,那就是环的入口。 建议:空想好难,建议... -
链表环路检测
2020-07-22 10:22:28给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 链表有环理解:如果链表中有环,那么快慢指针就一定可以相遇,... -
检测一个链表是否有环
2017-06-30 15:02:44定义两个指针fast、slow,其中,fast是快指针,slow是慢指针,二者的初始值都指向链表头, ... 否则,这个是不带环的链表(fast先行到达尾部为NULL,则为无环链表)。 代码: public boolean IsL -
算法之链表环路检测
2020-06-28 09:30:10给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [1,2,3,4], pos = 1 输出:tail ... -
链表的环路检测问题
2020-07-28 15:52:04给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:tail ... -
如何检测链表中是存在循环
2016-03-24 10:23:00这里出现的是其中一个题目,我称之为有环链表问题。也就是从判断一个单链表是否存在循环而扩展衍生的问题。下面来看问题如何解决。 首先来看最基本的这个问题:如何判断一个单链表是否存在循环,链表数目未知。算法... -
程序员面试经典--链表环路检测与入口结点返回
2017-04-09 19:33:15给定一个有环链表,实现一个算法返回环路的开头结点。 思考: 第一:监测链表是否存在环路。有一种简单的方法叫做fastrunner/slowrunner法。fastruner一次移动两步,slowrunner一次移动一步。如果存在环路,最终... -
Cracking the Coding Interview:: 寻找有环链表的环路起始节点
2013-12-25 13:07:15给定一个有环链表,实现一个算法返回环路的开头节点。 这个问题是由经典面试题-检测链表是否存在环路演变而来。 -
leetcode面试题 02.08. 环路检测
2020-06-14 18:41:13给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:tail ... -
环路检测
2020-03-11 22:27:19给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:tail ... -
02.08 环路检测
2020-11-07 21:33:27给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 ... -
力扣 环路检测
2020-12-08 17:09:08给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到... -
LeetCode:环路检测
2020-07-30 20:12:04给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 2. 示例 输入:head = [3,2,0,-4], pos = 1 输出:tail ... -
面试题 02.08. 环路检测
2020-04-28 12:26:28给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:tail ... -
python:环路检测
2020-08-22 00:33:15给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 ... -
程序员面试经典(9):环路检测
2020-03-01 21:44:46给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 我的解题 快慢指针 /** * Definition for singly-linked list... -
面试题 02.06. 环路检测
2020-02-28 10:49:52给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 /** * Definition for singly-linked list. * struct ... -
Leetcode--环路检测
2020-04-25 11:18:57给定一个有环链表,实现一个算法返回环路的开头节点。 有环链表的定义:在链表中某个节点的next元素指向在它前面出现过的节点,则表明该链表存在环路。 示例 1: 输入:head = [3,2,0,-4], pos = 1 输出:tail ...