\u7ed9\u4f60\u4e00\u4e2a\u94fe\u8868\u7684\u5934\u8282\u70b9\u00a0head，\u5224\u65ad\u94fe\u8868\u4e2d\u662f\u5426\u6709\u73af\u3002<\/p>\n
\u5982\u679c\u94fe\u8868\u4e2d\u6709\u67d0\u4e2a\u8282\u70b9，\u53ef\u4ee5\u901a\u8fc7\u8fde\u7eed\u8ddf\u8e2a\u00a0next\u00a0\u6307\u9488\u518d\u6b21\u5230\u8fbe，\u5219\u94fe\u8868\u4e2d\u5b58\u5728\u73af\u3002\u4e3a\u4e86\u8868\u793a\u7ed9\u5b9a\u94fe\u8868\u4e2d\u7684\u73af，\u8bc4\u6d4b\u7cfb\u7edf\u5185\u90e8\u4f7f\u7528\u6574\u6570\u00a0pos\u00a0\u6765\u8868\u793a\u94fe\u8868\u5c3e\u8fde\u63a5\u5230\u94fe\u8868\u4e2d\u7684\u4f4d\u7f6e（\u7d22\u5f15\u4ece 0 \u5f00\u59cb）\u3002\u6ce8\u610f：pos\u00a0\u4e0d\u4f5c\u4e3a\u53c2\u6570\u8fdb\u884c\u4f20\u9012，\u4ec5\u4ec5\u662f\u4e3a\u4e86\u6807\u8bc6\u94fe\u8868\u7684\u5b9e\u9645\u60c5\u51b5\u3002<\/p>\n
\u5982\u679c\u94fe\u8868\u4e2d\u5b58\u5728\u73af，\u5219\u8fd4\u56de\u00a0true\u3002\u5426\u5219，\u8fd4\u56de\u00a0false\u3002<\/p>\n
\u793a\u4f8b 1：<\/p>\n
text<\/p>\n
\u8f93\u5165：head = [3,2,0,-4], pos = 1
\n\u8f93\u51fa：true
\n\u89e3\u91ca：\u94fe\u8868\u4e2d\u6709\u4e00\u4e2a\u73af，\u5176\u5c3e\u90e8\u8fde\u63a5\u5230\u7b2c\u4e8c\u4e2a\u8282\u70b9\u3002<\/p>\n
\u793a\u4f8b 2：<\/p>\n
text<\/p>\n
\u8f93\u5165：head = [1,2], pos = 0
\n\u8f93\u51fa：true
\n\u89e3\u91ca：\u94fe\u8868\u4e2d\u6709\u4e00\u4e2a\u73af，\u5176\u5c3e\u90e8\u8fde\u63a5\u5230\u7b2c\u4e00\u4e2a\u8282\u70b9\u3002<\/p>\n
\u793a\u4f8b 3：<\/p>\n
text<\/p>\n
\u8f93\u5165：head = [1], pos = -1
\n\u8f93\u51fa：false
\n\u89e3\u91ca：\u94fe\u8868\u4e2d\u6ca1\u6709\u73af\u3002<\/p>\n
\u5224\u65ad\u94fe\u8868\u662f\u5426\u6709\u73af\u662f\u4e00\u4e2a\u7ecf\u5178\u7684\u94fe\u8868\u95ee\u9898，\u6700\u4f18\u96c5\u7684\u89e3\u51b3\u65b9\u6848\u662f\u4f7f\u7528\u5feb\u6162\u6307\u9488（Floyd's Cycle-Finding Algorithm）\u3002<\/p>\n
\u6162\u6307\u9488：\u6bcf\u6b21\u79fb\u52a8\u4e00\u6b65<\/p>\n<\/li>\n
\u5feb\u6307\u9488：\u6bcf\u6b21\u79fb\u52a8\u4e24\u6b65<\/p>\n<\/li>\n<\/ul>\n
\u5982\u679c\u94fe\u8868\u4e2d\u5b58\u5728\u73af，\u5feb\u6307\u9488\u6700\u7ec8\u4f1a\u8ffd\u4e0a\u6162\u6307\u9488（\u4e24\u8005\u76f8\u9047）；\u5982\u679c\u4e0d\u5b58\u5728\u73af，\u5feb\u6307\u9488\u4f1a\u5148\u5230\u8fbe\u94fe\u8868\u672b\u5c3e（NULL）\u3002<\/p>\n
c<\/p>\n
\/**
\n * Definition for singly-linked list.
\n * struct ListNode {
\n * int val;
\n * struct ListNode *next;
\n * };
\n *\/
\nbool hasCycle(struct ListNode *head) {
\n struct ListNode *fast = head;
\n struct ListNode *slow = head;<\/p>\n
while(fast && fast->next)
\n {
\n slow = slow->next; \/\/ \u6162\u6307\u9488\u79fb\u52a8\u4e00\u6b65
\n fast = fast->next->next; \/\/ \u5feb\u6307\u9488\u79fb\u52a8\u4e24\u6b65<\/p>\n
if(slow == fast) \/\/ \u5982\u679c\u76f8\u9047，\u8bf4\u660e\u6709\u73af
\n return true;
\n }<\/p>\n
return false; \/\/ \u5feb\u6307\u9488\u5230\u8fbe\u672b\u5c3e，\u8bf4\u660e\u65e0\u73af
\n}<\/p>\n
c<\/p>\n
while(fast && fast->next)
\n{
\n slow = slow->next; \/\/ \u6162\u6307\u9488\u79fb\u52a8\u4e00\u6b65
\n fast = fast->next->next; \/\/ \u5feb\u6307\u9488\u79fb\u52a8\u4e24\u6b65<\/p>\n
if(slow == fast) \/\/ \u68c0\u67e5\u662f\u5426\u76f8\u9047
\n return true;
\n}<\/p>\n
\u5faa\u73af\u6761\u4ef6\u5206\u6790：<\/p>\n
fast：\u786e\u4fdd\u5feb\u6307\u9488\u672c\u8eab\u4e0d\u4e3a\u7a7a<\/p>\n<\/li>\n
fast->next：\u786e\u4fdd\u5feb\u6307\u9488\u53ef\u4ee5\u5b89\u5168\u5730\u79fb\u52a8\u4e24\u6b65<\/p>\n<\/li>\n<\/ul>\n
\u6709\u73af\u7684\u60c5\u51b5（\u793a\u4f8b1）：<\/p>\n
text<\/p>\n
\u94fe\u8868：3 -> 2 -> 0 -> -4 -> 2（\u5f62\u6210\u73af）<\/p>\n
\u521d\u59cb：slow -> 3, fast -> 3<\/p>\n
\u7b2c1\u6b21\u5faa\u73af：
\nslow -> 2, fast -> 0
\n\u6bd4\u8f83：2 != 0<\/p>\n
\u7b2c2\u6b21\u5faa\u73af：
\nslow -> 0, fast -> 2
\n\u6bd4\u8f83：0 != 2<\/p>\n
\u7b2c3\u6b21\u5faa\u73af：
\nslow -> -4, fast -> -4
\n\u6bd4\u8f83：-4 == -4 \u2192 \u8fd4\u56detrue<\/p>\n
\u65e0\u73af\u7684\u60c5\u51b5：<\/p>\n
text<\/p>\n
\u94fe\u8868：1 -> 2 -> 3 -> 4 -> NULL<\/p>\n
\u521d\u59cb：slow -> 1, fast -> 1<\/p>\n
\u7b2c1\u6b21\u5faa\u73af：
\nslow -> 2, fast -> 3
\n\u6bd4\u8f83：2 != 3<\/p>\n
\u7b2c2\u6b21\u5faa\u73af：
\nslow -> 3, fast -> NULL
\n\u6761\u4ef6\u5224\u65ad：fast == NULL \u2192 \u9000\u51fa\u5faa\u73af，\u8fd4\u56defalse<\/p>\n
\u5047\u8bbe\u94fe\u8868\u73af\u5916\u90e8\u5206\u957f\u5ea6\u4e3a\u00a0L，\u73af\u7684\u5468\u957f\u4e3a\u00a0C\u3002<\/p>\n
\u5f53\u6162\u6307\u9488\u8fdb\u5165\u73af\u65f6：<\/p>\n
\u6162\u6307\u9488\u4f4d\u7f6e：0（\u73af\u7684\u8d77\u70b9）<\/p>\n<\/li>\n
\u5feb\u6307\u9488\u4f4d\u7f6e：L % C（\u56e0\u4e3a\u5feb\u6307\u9488\u5df2\u7ecf\u8d70\u4e86\u00a02L\u00a0\u6b65）<\/p>\n<\/li>\n<\/ul>\n
\u5feb\u6307\u9488\u76f8\u5bf9\u4e8e\u6162\u6307\u9488\u7684\u901f\u5ea6\u662f 1 \u6b65\/\u5355\u4f4d\u65f6\u95f4（\u5feb\u6307\u9488\u6bd4\u6162\u6307\u9488\u5feb\u4e00\u6b65），\u6240\u4ee5\u5feb\u6307\u9488\u9700\u8981\u8ffd\u8d76\u7684\u8ddd\u79bb\u6700\u591a\u4e3a\u00a0C-1\u00a0\u6b65\u3002<\/p>\n
\u56e0\u6b64，\u5728\u00a0C-1\u00a0\u6b21\u5faa\u73af\u5185，\u5feb\u6307\u9488\u4e00\u5b9a\u4f1a\u8ffd\u4e0a\u6162\u6307\u9488\u3002<\/p>\n
\u6162\u6307\u9488\u6700\u591a\u8d70\u00a0L + C\u00a0\u6b65（\u73af\u5916\u957f\u5ea6 + \u73af\u5468\u957f）<\/p>\n<\/li>\n
\u5feb\u6307\u9488\u6700\u591a\u8d70\u00a02(L + C)\u00a0\u6b65<\/p>\n<\/li>\n
\u65f6\u95f4\u590d\u6742\u5ea6：O(n)，\u5176\u4e2d n \u662f\u94fe\u8868\u957f\u5ea6<\/p>\n<\/li>\n<\/ul>\n
c<\/p>\n
#include <stdbool.h><\/p>\n
bool hasCycle(struct ListNode *head) {
\n struct ListNode *visited[10000] = {0}; \/\/ \u7b80\u5355\u7684\u54c8\u5e0c\u8868
\n int count = 0;<\/p>\n
struct ListNode *current = head;
\n while (current != NULL) {
\n \/\/ \u68c0\u67e5\u5f53\u524d\u8282\u70b9\u662f\u5426\u5df2\u7ecf\u8bbf\u95ee\u8fc7
\n for (int i = 0; i < count; i++) {
\n if (visited[i] == current) {
\n return true;
\n }
\n }<\/p>\n
\/\/ \u8bb0\u5f55\u5df2\u8bbf\u95ee\u7684\u8282\u70b9
\n visited[count++] = current;
\n current = current->next;
\n }<\/p>\n
return false;
\n}<\/p>\n
\u4f18\u7f3a\u70b9：<\/p>\n
\u4f18\u70b9：\u601d\u8def\u7b80\u5355\u76f4\u89c2<\/p>\n<\/li>\n
\u7f3a\u70b9：\u7a7a\u95f4\u590d\u6742\u5ea6 O(n)，\u9700\u8981\u5b58\u50a8\u6240\u6709\u8bbf\u95ee\u8fc7\u7684\u8282\u70b9<\/p>\n<\/li>\n<\/ul>\n
c<\/p>\n
bool hasCycle(struct ListNode *head) {
\n struct ListNode *current = head;<\/p>\n
while (current != NULL) {
\n \/\/ \u5982\u679c\u9047\u5230\u7279\u6b8a\u6807\u8bb0\u503c，\u8bf4\u660e\u6709\u73af
\n if (current->val == 1000000) {
\n return true;
\n }<\/p>\n
\/\/ \u6807\u8bb0\u5f53\u524d\u8282\u70b9（\u5047\u8bbe\u8282\u70b9\u503c\u4e0d\u4f1a\u7b49\u4e8e1000000）
\n current->val = 1000000;
\n current = current->next;
\n }<\/p>\n
return false;
\n}<\/p>\n
\u4f18\u7f3a\u70b9：<\/p>\n
\u4f18\u70b9：\u7a7a\u95f4\u590d\u6742\u5ea6 O(1)<\/p>\n<\/li>\n
\u7f3a\u70b9：\u4fee\u6539\u4e86\u539f\u59cb\u94fe\u8868\u6570\u636e，\u4e0d\u63a8\u8350\u5728\u5b9e\u9645\u4e2d\u4f7f\u7528<\/p>\n<\/li>\n<\/ul>\n
\u65f6\u95f4\u590d\u6742\u5ea6：O(n)，\u6700\u574f\u60c5\u51b5\u4e0b\u9700\u8981\u904d\u5386\u6574\u4e2a\u94fe\u8868<\/p>\n<\/li>\n
\u7a7a\u95f4\u590d\u6742\u5ea6：O(1)，\u53ea\u4f7f\u7528\u4e24\u4e2a\u6307\u9488\u53d8\u91cf<\/p>\n<\/li>\n<\/ul>\n
\u65f6\u95f4\u590d\u6742\u5ea6：O(n)，\u9700\u8981\u904d\u5386\u94fe\u8868<\/p>\n<\/li>\n
\u7a7a\u95f4\u590d\u6742\u5ea6：O(n)，\u9700\u8981\u5b58\u50a8\u6240\u6709\u8bbf\u95ee\u8fc7\u7684\u8282\u70b9<\/p>\n<\/li>\n<\/ul>\n
c<\/p>\n
struct ListNode *detectCycle(struct ListNode *head) {
\n struct ListNode *slow = head;
\n struct ListNode *fast = head;<\/p>\n
\/\/ \u7b2c\u4e00\u9636\u6bb5：\u5224\u65ad\u662f\u5426\u6709\u73af
\n while (fast && fast->next) {
\n slow = slow->next;
\n fast = fast->next->next;<\/p>\n
if (slow == fast) {
\n \/\/ \u7b2c\u4e8c\u9636\u6bb5：\u627e\u5230\u73af\u7684\u5165\u53e3
\n struct ListNode *ptr1 = head;
\n struct ListNode *ptr2 = slow;<\/p>\n
while (ptr1 != ptr2) {
\n ptr1 = ptr1->next;
\n ptr2 = ptr2->next;
\n }<\/p>\n
return ptr1; \/\/ \u73af\u7684\u5165\u53e3\u8282\u70b9
\n }
\n }<\/p>\n
return NULL; \/\/ \u65e0\u73af
\n}<\/p>\n
\u539f\u7406：<\/p>\n
\u5feb\u6162\u6307\u9488\u76f8\u9047\u65f6，\u6162\u6307\u9488\u8d70\u4e86\u00a0L + S\u00a0\u6b65，\u5feb\u6307\u9488\u8d70\u4e86\u00a0L + S + nC\u00a0\u6b65<\/p>\n<\/li>\n
\u7531\u4e8e\u5feb\u6307\u9488\u901f\u5ea6\u662f\u6162\u6307\u9488\u7684\u4e24\u500d：2(L + S) = L + S + nC<\/p>\n<\/li>\n
\u7b80\u5316\u5f97：L = nC – S<\/p>\n<\/li>\n
\u8fd9\u610f\u5473\u7740\u4ece\u5934\u90e8\u8d70\u5230\u73af\u5165\u53e3\u7684\u8ddd\u79bb\u7b49\u4e8e\u4ece\u76f8\u9047\u70b9\u8d70\u5230\u73af\u5165\u53e3\u7684\u8ddd\u79bb<\/p>\n<\/li>\n
\u5feb\u6162\u6307\u9488\u6280\u5de7\u5728\u5f88\u591a\u573a\u666f\u4e2d\u90fd\u6709\u5e94\u7528：<\/p>\n
\u5224\u65ad\u94fe\u8868\u662f\u5426\u6709\u73af（\u672c\u9898）<\/p>\n<\/li>\n
\u627e\u5230\u73af\u7684\u5165\u53e3\u8282\u70b9<\/p>\n<\/li>\n
\u627e\u5230\u94fe\u8868\u7684\u4e2d\u95f4\u8282\u70b9<\/p>\n<\/li>\n
\u5224\u65ad\u4e24\u4e2a\u94fe\u8868\u662f\u5426\u76f8\u4ea4<\/p>\n<\/li>\n
\u627e\u5230\u94fe\u8868\u7684\u5012\u6570\u7b2c k \u4e2a\u8282\u70b9<\/p>\n<\/li>\n
\u5224\u65ad\u94fe\u8868\u662f\u5426\u6709\u73af\u662f\u4e00\u4e2a\u7ecf\u5178\u7684\u94fe\u8868\u95ee\u9898，\u5feb\u6162\u6307\u9488\u6cd5\u662f\u6700\u4f18\u89e3：<\/p>\n
\u6838\u5fc3\u601d\u60f3：\u5feb\u6307\u9488\u901f\u5ea6\u662f\u6162\u6307\u9488\u7684\u4e24\u500d，\u5982\u679c\u6709\u73af，\u4e24\u8005\u4e00\u5b9a\u4f1a\u76f8\u9047<\/p>\n<\/li>\n
\u6548\u7387\u4f18\u52bf：\u65f6\u95f4\u590d\u6742\u5ea6 O(n)，\u7a7a\u95f4\u590d\u6742\u5ea6 O(1)<\/p>\n<\/li>\n
\u8fb9\u754c\u5904\u7406：\u6ce8\u610f\u5904\u7406\u7a7a\u94fe\u8868\u548c\u5355\u8282\u70b9\u94fe\u8868\u7684\u60c5\u51b5<\/p>\n<\/li>\n
\u5faa\u73af\u6761\u4ef6：\u786e\u4fdd\u5feb\u6307\u9488\u53ef\u4ee5\u5b89\u5168\u5730\u79fb\u52a8\u4e24\u6b65<\/p>\n<\/li>\n
\u638c\u63e1\u5feb\u6162\u6307\u9488\u6280\u5de7\u5bf9\u4e8e\u89e3\u51b3\u94fe\u8868\u76f8\u5173\u95ee\u9898\u975e\u5e38\u6709\u5e2e\u52a9，\u8fd9\u662f\u9762\u8bd5\u4e2d\u5e38\u89c1\u7684\u8003\u70b9\u4e4b\u4e00\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u9898\u76ee\u63cf\u8ff0\u7ed9\u4f60\u4e00\u4e2a\u94fe\u8868\u7684\u5934\u8282\u70b9\u00a0head，\u5224\u65ad\u94fe\u8868\u4e2d\u662f\u5426\u6709\u73af\u3002\u5982\u679c\u94fe\u8868\u4e2d\u6709\u67d0\u4e2a\u8282\u70b9，\u53ef\u4ee5\u901a\u8fc7\u8fde\u7eed\u8ddf\u8e2a\u00a0next\u00a0\u6307\u9488\u518d\u6b21\u5230\u8fbe，\u5219\u94fe\u8868\u4e2d\u5b58\u5728\u73af\u3002\u4e3a\u4e86\u8868\u793a\u7ed9\u5b9a\u94fe\u8868\u4e2d\u7684\u73af，\u8bc4\u6d4b\u7cfb\u7edf\u5185\u90e8\u4f7f\u7528\u6574\u6570\u00a0pos\u00a0\u6765\u8868\u793a\u94fe\u8868\u5c3e\u8fde\u63a5\u5230\u94fe\u8868\u4e2d\u7684\u4f4d\u7f6e（\u7d22\u5f15\u4ece 0 \u5f00\u59cb）\u3002\u6ce8\u610f：pos\u00a0\u4e0d\u4f5c\u4e3a\u53c2\u6570\u8fdb\u884c\u4f20\u9012，\u4ec5\u4ec5\u662f\u4e3a\u4e86\u6807\u8bc6\u94fe\u8868\u7684\u5b9e\u9645\u60c5\u51b5\u3002\u5982\u679c\u94fe\u8868\u4e2d\u5b58\u5728\u73af，\u5219\u8fd4\u56de\u00a0true\u3002\u5426\u5219&#<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[174,89,92,790,190,1813,2640],"topic":[],"class_list":["post-78294","post","type-post","status-publish","format-standard","hentry","category-server","tag-c","tag-git","tag-github","tag-visual-studio","tag-190","tag-1813","tag-2640"],"yoast_head":"\n