C语言数据结构：环形链表要点

C语言数据结构环形链表要点环形链表题目解析环形链表II题目解析要点问题一一定能相遇吗问题二如果fast走其他步能追上吗问题三如何找到环的第一个节点环形链表题目环型链表解析分析可知环有大有小判断是否有环的办法使用快慢指针快指针走两步慢指针走一步当快慢指针相遇时说明链表有环得到程序代码typedefstructListNodeListNode;boolhasCycle(structListNode*head){ListNode*fast,*slow;fastslowhead;while(fastfast-next){slowslow-next;fastfast-next-next;if(fastslow)returntrue;}returnfalse;}环形链表II题目环形链表II题目要求返回环的第一个节点无环返回NULL解析两个步骤1. 判断是否有环 2. 有环返回环的第一个节点对于步骤1前面已经解答对于步骤2解析如下快慢指针第一次相遇的节点为meet一个指针从链表的头节点head开始走一个指针从meet节点开始走两个指针相遇处就是环的入口处稍后证明得到本题代码// 1. 判断是否存在环 2. 返回环的入口节点typedefstructListNodeListNode;structListNode*detectCycle(structListNode*head){// 1. 快慢指针判断是否存在环// fast 2*slowListNode*fast,*slow;fastslowhead;while(fastfast-next){slowslow-next;fastfast-next-next;// 快慢指针相遇, 存在环if(slowfast){// 2. 返回环的入口节点ListNode*meetslow;ListNode*pcurhead;while(meet!pcur){meetmeet-next;pcurpcur-next;}returnmeet;}}// 快指针访问到NULL,不存在环returnNULL;}要点在一定有环存在的情况下存在两个疑问为什么两个指针一定会相遇有没有可能会错过永远追不上请证明如果fast改为一次走 3 / 4 / 5 …… n 步还一定能追上吗为什么请证明问题一一定能相遇吗为什么一定会相遇有没有可能会错过永远追不上为什么请证明假设 slow 刚进环时 fast 与 slow 之间的距离为 Nfast 每次走两步slow 每次走一步每追击一次fast 与 slow 之间的距离就缩短 1fast 与 slow 之间的距离变化为 N N - 1 N - 2 N - 3 …… 2 1 0当 fast 与 slow 之间的距离为 0 时就是追上了问题二如果fast走其他步能追上吗如果 slow 走一步fast 走 3 / 4 / 5 ……n 步还一定能追上吗请证明此处只证明 fast 走 3 步时其余方法一致假设slow进入环中时fast与slow的距离为N环的周长为C从链表头节点phead开始到环节点的距离为Lfast 与 slow 之间的距离变化为 N为偶数 N为奇数 N N N - 2 N - 2 N - 4 N - 4 N - 6 N - 6 …… …… 4 3 2 1 0 -1当fast与slow之间的距离为0时表示追上了当fast与slow之间的距离为-1时表明错过了开始新的一轮追击此时fast与slow之间的距离为C-1此时fast与slow之间的距离为C-1 fast与slow之间的距离变化如下 C为奇数 C为偶数 C - 1 C - 1 C - 3 C - 3 C - 5 C - 5 …… …… 4 3 2 1 0 -1当fast与slow之间的距离为0时表示追上了当fast与slow之间的距离为-1时表明错过了开始重复追击此时fast与slow之间的距离为C-1将循环追击永远追不上总结当 N 为偶数时第一轮追击就追上了当 N 为奇数时第一轮追击会错过fast 与 slow 之间的距离变成 C - 1如果 C - 1 为偶数第二轮追上如果 C - 1 为奇数永远追不上如果同时存在 N 为奇数 且 C 为偶数那么就永远追不上问存在这种情况吗slow 进入环中时fast 与 slow 的距离为 N环的周长为 C从链表头节点 phead 开始到环节点的距离为 L假设 slow 进环时fast 已经在环内转了 x 圈slow 进环时 slow 走的距离L fast 走的距离 Lx*CC-N 已知fast 走的距离时 slow 的三倍 3L Lx*CC-N 化简得2L (x1)*C-N已知永远追不上的条件为1. N 为奇数 2. C 为偶数所以代入 2L (x1)*C-N 中得偶数 (x1)*偶数 - 奇数 偶数*任何数都是偶数 偶数-奇数 奇数 再次化简为偶数 偶数 - 奇数所以等式两边不相等N 为奇数和 C 为偶数的情况不能同时存在永远追不上的情况不存在N 是奇数时C 为奇数N 是偶数时C 为偶数结论一定追得上N 为偶数时第一轮就追上了N 为奇数时第二轮才能追上(第一轮错过开始第二轮追击第二轮追击距离为C-1C-1为偶数第二轮追上)问题三如何找到环的第一个节点一个指针从链表头节点phead处开始走一个指针从快慢指针第一次相遇的节点meet开始走两个指针相遇的节点为什么就是环的入口点处请证明假设快慢指针相遇时从链表头节点到环的入口点的距离为 L环的周长为 C快指针 fast 已经在环内转了 x 圈快慢指针相遇点到环的入口点的距离为 N注意 慢指针slow不可能在环中走超过1圈原因 慢指针入环时快慢指针之间只有环的初始距离当慢指针走满一圈时fast已经在环内走了两圈早就已经超过了初始距离注意快指针在环内转了 x 圈x 必然 ≥ 1即快指针至少在环内走了 1 圈原因慢指针进入环时快指针已经进入环了当快指针追上慢指针时最少要在环内走一圈slow 走的距离: L N fast 走的距离: L x*C N 已知: fast 2*slow 2*(L N) L x*C N 化简得: L x*C - N -- L (x - 1)*C C - N (x - 1)*C 即在环内转了 x-1 圈 C - N 正好是从 meet 节点到环的入口处的距离由此可得当从头节点phead开始走的指针走到环的入口处时从meet处开始走的指针正好绕道环的入口处