思路1(思路难、代码简单):
slow一次走一步,fast一次走两步;相遇时搞个meet,再搞一个head,head和meet一起走,每次走一步;head、meet相遇处,即为结果。
思路解释:
当相遇时,slow走的路程:L+N;当相遇时,fast走的路程L+x*C+N。(x指fast走过的圈数,x>0)
这时,可能有爱发问的读者有了疑惑:slow在1圈以内就能和fast相遇吗?
答:of course。首先,slow和fast肯定能够相遇;若slow和fast相距M,那么随着两指针移动,M不断变小,直到变为0相遇。然后,因为fast的速度是slow是两倍;如果slow走完一圈,此时fast已经走完了两圈,然而slow和fast不会出现错过不能相遇的情况。综上所述,slow肯定能在1圈以内和fast相遇。
因为fast走的路程是slow2倍,故得公式:2*(L+N) = L + x*C + N
化简以后,得 L = x*C - N
当x为1时,meet 和 head 都相距入环的第一个结点 C - N 的距离。
当x>1时,meet相距入环第一个结点 (x-1)*C + C - N,较于上一种情况,只是多转了几圈,并无二致。
代码:
struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow=head,*fast=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;if(slow == fast){struct ListNode* meet=slow;while(meet != head){meet = meet->next;head = head->next;}return meet;}}return NULL;
}
思路2(思路简单、代码量比较大):
注:该思路基于思路1
slow、fast相遇后,定义一个newhead,且 newhead = meet->next,然后将meet->next置空。操作执行完毕后,效果如上图所示。
此时,我们就能看到一个Y字型,不难想到相交链表。
(相交链表讲解文章:相交链表讲解)
因此,直接使用相交链表的函数完成操作。
代码:
typedef struct ListNode listnode;typedef struct ListNode listnode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {listnode* curA,*curB;curA = headA,curB = headB;int lenA = 1,lenB = 1;while(curA->next){curA = curA->next;lenA++;}while(curB->next){curB=curB->next;lenB++;}if(curA != curB)return NULL;int gap = abs(lenA - lenB);listnode* longlist = headA,* shortlist = headB;if(lenB > lenA){longlist = headB;shortlist = headA;}while(gap--){longlist = longlist -> next;}while(longlist != shortlist){longlist = longlist->next;shortlist = shortlist->next;}return shortlist;
}
struct ListNode *detectCycle(struct ListNode *head)
{listnode* fast=head,*slow=head;while(fast && fast->next){slow=slow->next;fast=fast->next->next;if(slow == fast){listnode* next = slow->next;slow->next=NULL;return getIntersectionNode(head,next);}}return NULL;
}