判断链表有环,环的入口结点,环的长度
1.判断有环:
快慢指针,一个移动一次,一个移动两次
2.环的入口结点:
相遇的结点不一定是入口节点,所以y表示入口节点到相遇节点的距离
n是环的个数
- w + n + y = 2 (w + y)
经过化简,我们可以得到:w = n - y;
https://www.cnblogs.com/zhuzhenwei918/p/7491892.html
3.环的长度:
从入口结点或者相遇的结点移动到下一次再碰到这个结点计数
https://blog.csdn.net/jyy305/article/details/75267969
141. Linked List Cycle
使用快慢指针,一个一次滑动一次,一个一次滑动两次。
如果只是判断有没有环,初始化可以不两个都初始化到head,但为了方便和找入口节点那个题的记忆,都初始化为head。
两个都初始化为head,就不能先把if(p1 == p2)放在while循环的开始,要放在迭代之后。
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL)
return false;
//ListNode* p1 = head,p2 = head;
ListNode* p1 = head;
ListNode* p2 = head;
while(p2 != NULL && p2->next != NULL){
p1 = p1->next;
p2 = p2->next->next;
if(p1 == p2)
return true;
}
return false;
}
};
142. Linked List Cycle II
两个指针初始化必须初始化在head的地方,这样才能使用后面推导的公式https://www.cnblogs.com/ymjyqsx/p/9568129.html
在head申明一个新的节点,一个一个滑动,然后p1也是一个一个滑动,相遇的节点就是入口节点
head->next == NULL是为了避免[1]这种情况
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == NULL)
return NULL;
if(head->next == NULL)
return NULL;
ListNode* p1 = head;
ListNode* p2 = head;
while(p2 != NULL && p2->next != NULL){
p1 = p1->next;
p2 = p2->next->next;
if(p1 == p2)
break;
}
if(p1 != p2){
return NULL;
}
ListNode* p3 = head;
while(p1 != p3){
p1 = p1->next;
p3 = p3->next;
}
return p1;
}
};