一、题意
二、思考过程
这道题不仅考察对链表的操作，而且还需要一些数学运算。
主要考察两知识点：
- 判断链表是否有环
- 如果有环，如何找到这个环的入口
以上两个为数学问题。
2.1判断链表是否有环
可以使用快慢指针法，分别定义 FastIndex指针和 SlowIndex指针，从头结点出发，FastIndex指针每次移动两个节点， SlowIndex指针每次移动一个节点，如果 FastIndex指针和 SlowIndex指针在途中相遇，说明这个链表有环。
FastIndex指针：走两步
SlowIndex指针：走一步
while(FastIndex&&FastIndex->next){ SlowIndex=SlowIndex->next;//慢指针走一步 FastIndex=FastIndex->next->next;//快指针走两步
2.2寻找环的入口
这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
在相遇节点处，定义一个指针f，在头结点处定一个指针h。
让 f 和 h 同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。
if(SlowIndex==FastIndex){ ListNode *f=FastIndex; ListNode *h=head; while(f!=h) { f=f->next; h=h->next; } return h;//环形入口节点 } }
三、完整代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { typedef struct ListNode ListNode; ListNode *FastIndex=head; ListNode *SlowIndex=head; while(FastIndex&&FastIndex->next){ SlowIndex=SlowIndex->next; FastIndex=FastIndex->next->next; if(SlowIndex==FastIndex){ ListNode *f=FastIndex; ListNode *h=head; while(f!=h) { f=f->next; h=h->next; } return h; } } return NULL; }
