给定一个链表,如果链表中存在环,则返回到链表中环的起始节点的值,如果没有环,返回null。
思路详解
class Solution {
public:
/**
* @param head: The first node of linked list.
* @return: The node where the cycle begins.
* if there is no cycle, return null
*/
ListNode *detectCycle(ListNode *head) {
// write your code here
if (!head || !head->next) {
return NULL;
}
ListNode *fast = head;
ListNode *slow = head;
while(fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
if(fast == slow) {
ListNode *temp = head;
while(fast != temp) {
temp = temp->next;
fast = fast->next;
}
return fast;
}
}
return NULL;
}
};