首页 > 代码库 > leetcode. Linked List Cycle && Linked List Cycle ii
leetcode. Linked List Cycle && Linked List Cycle ii
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
使用双指针fast和slow，fast每次走两步，slow每次走一步，如果fast追上slow则存在环，否则不存在。
1 bool hasCycle(ListNode *head) 2 { 3 ListNode *slow = head, *fast = head; 4 while (fast != NULL) 5 { 6 slow = slow->next; 7 fast = fast->next; 8 if (fast != NULL) 9 fast = fast->next;10 if (fast != NULL && fast == slow)11 return true;12 }13 14 return false;15 }
Linked List Cycle ii则是要求出环出现的那个节点。
在fast追上slow时，fast比slow多走了nC，n>=1, C为圆的周长。如下图：
slow走的路程：lenA + x，fast走的路程：LenA + nC + x
因为fast走的路程是slow的两倍：2(lenA + x) = lenA + nC + x
于是, nC = lenA + x, 即lenA = nC - x。
那么相遇时，让slow指向head，fast和slow走一样的步长，最终相遇在Join处。
1 ListNode *detectCycle(ListNode *head) 2 { 3 ListNode *fast = head, *slow = head; 4 5 while (fast != NULL) 6 { 7 slow = slow->next; 8 fast = fast->next; 9 if (fast != NULL)10 fast = fast->next;11 if (fast != NULL && fast == slow)12 break;13 }14 15 if (fast == NULL)16 return NULL;17 18 slow = head;19 while (slow != fast)20 {21 slow = slow->next;22 fast = fast->next;23 }24 25 return slow;26 }
leetcode. Linked List Cycle && Linked List Cycle ii
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。