leetcode141.环形链表，142环形链表ii

目录 问题描述示例提示 具体思路思路一 代码实现问题描述具体思路思路一思路二

问题描述

给你一个链表的头节点 head ，判断链表中是否有环。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 ，则返回 true 。 否则，返回 false 。

题目链接：环形链表1

示例

提示

  链表中节点的数目范围是 [0, 104]   -105 <= Node.val <= 105   pos 为 -1 或者链表中的一个 有效索引 。

具体思路 思路一

环形链表1 1、slow和fast一定会相遇吗？ 一定会，fast会先进环，slow会后进环，假设slow进环时，slow和fast之间的距离为N slow进环以后，fast开始追击slow，slow每走1步，fast每走2步，他们之间距离缩小1。 N N-1 N-2 N-3 N-4 … 2 1 0

2、slow走1步，fast走n(3/4/5…)步可以吗？(n>2) 不一定，fast会先进环，slow会后进环，假设slow进环时，slow和fast之间的距离为N slow进环以后，fast开始追击slow，slow每走1步，fast每走3步，他们之间距离缩小2。 N N-2 N-4 N-6 … 4 2 0 N是偶数就会相遇。N是奇数就会错过，会进入新一轮的追击，slow和fast的距离变成C-1（假设C是环的长度） 如果C-1是偶数那么下一轮可以追上 如果C-1是奇数那么永远追不上

代码实现 //思路1 /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode* slow=head; struct ListNode* fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) return true; } return false; } 问题描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。 不允许修改 链表。

题目链接：环形链表2

具体思路 思路一

转换为相交链表的问题，将meetNext=meet->next，meet->next=NULL。然后使用相交链表的问题求解相交的交点

思路二

环形链表2 fast走的路程是slow的2倍 假设：链表头–环入口点距离：L 环入口点–距离点距离:X 环的长度：C

slow走的路程是多少：L+X -> 分析，有没有可能slow进环转了几圈才追上？不可能！1圈之内，fast必然追上slow，因为他们之间距离每次缩小1，不会错过，slow走1圈，fast都走了2圈了，肯定追上了。

fast走的路程是多少：L+nC+X

2*(L+X)=L+nC+X L+X=nC L=nC-X n是slow进环前，fast在环里面转的圈数

所以一个指针从相遇点走，一个指针从链表头开始走，他们会在入口点相遇

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow=head; struct ListNode* fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) { struct ListNode* meet=slow; while(head!=meet) { head=head->next; meet=meet->next; } return meet; } } return NULL; }