leetcode 141. Linked List Cycle 、 142. Linked List Cycle II

判断链表有环,环的入口结点,环的长度

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;
}
};
上一篇:简短的几句js实现css压缩和反压缩功能


下一篇:JDK源码分析(8) StringBuffer & StringBuilder