题目描述
判断单链表中是否存在环,如果存在就输出环的入口结点,否则输出NULL
思路:
- 设置两个快慢指针,快的每次走两步,慢的每次走一步
- 如果存在环,那么快慢指针一定会相遇
- 相遇的时候,就重新设置一个指针,指回初始结点,然后慢指针不动
- 接下来两者每次都走一步,当两者相遇时,就是环的入口结点
PS:对于这道题,表面上是链表的题,其实是一道数学的证明题,读者可以再网上搜索本题的证明。
C代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode LNode;
struct ListNode *entryNodeOfLoop(struct ListNode *head) {
LNode *fast = head,*slow = head;//设置两个快慢指针
while(fast&& fast->next){
slow = slow->next;//慢指针每次走一步
if(!fast->next) return NULL;
fast = fast->next->next;//快指针每次走两步
if(fast == slow){//如果快慢指针相遇,表明存在环
LNode *p1 = head;//此时就让一个指针重新回到初始位置
while(p1 != slow){//之后这两个指针同时移动(每次都走一步),当他们相遇时,就是环入口结点
p1 = p1->next;
slow = slow->next;
}
return p1;//返回入口结点
}
}
return NULL;
}