思路
两次循环,第一次循环是快慢指针,若链表不是环形,则快指针先到表尾NULL,若是环形,快慢指针会相遇。相遇后将快慢指针之一置到表头head,然后开始第二次循环,此时快慢指针同速移动。当快慢指针再次相遇时到达链表开始入环的第一个节点。
代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode *slow = head;// 定义两个指针,一个快指针,一个慢指针,都从头开始 ListNode * fast = head; while(fast!=NULL&& fast->next!=NULL) { fast=fast->next->next;//快指针每次跑两步 slow = slow->next;//慢指针每次跑一步 if(slow==fast)//第一次相遇,则 { fast = head;//快指针从头开始运动 直到两个指针第二次相遇 则为入口环的节点 while(fast!=slow) { fast= fast->next; slow = slow->next; } return fast; break; } } return NULL; } };