题目要求
给定一个链表,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 如果链表中存在环,则返回入环的结点
。 否则,返回NULL。
思路
设置快慢指针,快指针一次走两步,慢指针一次走一步,如果有环,快慢指针同时进环后,快指针会追上慢指针,他们的地址会相等,然后,从快慢指针相遇处和链表的头结点处,分别出发两个指针,均走一步,两个指针会在入环处相遇,返回该结点即可。
图解
代码实现
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode * fast =
head; struct ListNode * slow = head; while (fast && fast->next) { fast =
fast->next->next; slow = slow->next; if (fast == slow) { struct ListNode*
slowHead = head; while (slow != slowHead) { slow = slow->next; slowHead =
slowHead->next; } return slow; } } return NULL; }