1 class Solution { 2 public: 3 ListNode *detectCycle(ListNode *head) { 4 set<ListNode *> node_set; 5 while (head) { 6 if (node_set.find(head) != node_set.end()) { 7 return head; 8 } 9 node_set.insert(head); 10 head = head->next; 11 } 12 return NULL; 13 } 14 };
思路 2 快慢指针
设: 1)绿色 2,3 段为 a 2)蓝色 4,5,6 段为 b 3)红色 7,3 段为 c slow = a+b fast = a+b+c+b fast 的路程是 slow 的两倍: 2*(a+b)= a+b+c+b >> a = c(有环,这两段是相等的)从 head 与 meet 出发,两指针速度一样,相遇即环的起点
1 class Solution { 2 public: 3 ListNode *detectCycle(ListNode *head) { 4 ListNode *fast = head; 5 ListNode *slow = head; 6 ListNode *meet = NULL;//相遇的节点 7 8 while (fast) { 9 slow = slow->next;//各走一步 10 fast = fast->next; 11 if (!fast) {//fast到了尾部,说明不是环形 12 return NULL; 13 } 14 fast = fast->next; 15 if (fast == slow) { 16 meet = fast; 17 break; 18 } 19 } 20 if (meet == NULL) { 21 return NULL; 22 } 23 while (head && meet) {//能到这里说明一定有环,条件(true) 24 if (head == meet) { 25 return head;//相遇即环的起点 26 } 27 head = head->next; 28 meet = meet->next; 29 } 30 return NULL;// 31 } 32 };