LeetCode Linked List Cycle II

LeetCode Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?


本题在LeetCode Linked List Cycle的基础上更进一步,需要求出链表中环的起点位置。
接上一题,相遇位置在Z,此时如果令slower=head,然后slower和faster都以相同的速度走a步,则slower刚好能到环的起点位置Y,那么faster会在哪里呢。
上一题推出来相遇的时候有:a+b=(n-2m)c,如果faster在相遇点走a步,则相当于走了a=(n-2m)c-b,(n-2m)c相当于绕圈n-2m次,(n-2m)c-b的意思就是在z点绕圈n-2m次的基础上,退回b步,看图,退回b步正好到达了环的起点Y。
所以快慢指针再走a步之后,正好在环的起点相遇了!
于是本题的思路就是:先用上一题的方法找到相遇位置,然后slower回到head节点,slower和faster都再次单步走,再次相遇时,就是环的起点。
完整代码如下:

class Solution {
public:
	ListNode *detectCycle(ListNode *head) {
		if (head == NULL || head->next == NULL)return NULL;
		ListNode *faster = head, *slower = head;
		while (faster->next != NULL&&faster->next->next != NULL) {
			faster = faster->next->next;
			slower = slower->next;
			if (faster == slower)break;
		}
		if (faster->next == NULL || faster->next->next == NULL)return NULL;
		slower = head;
		while (slower != faster) {
			slower = slower->next;
			faster = faster->next;
		}
		return slower;
	}
};

本代码提交AC,用时13MS。

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.