给定一个链表,如果链表中存在环,则返回到链表中环的起始节点的值,如果没有环,返回null。
/**
* Definition of ListNode
* class ListNode {
* public:
* int val;
* ListNode *next;
* ListNode(int val) {
* this->val = val;
* this->next = 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 == NULL || head->next == NULL) { return NULL; }
ListNode * front = head;
ListNode * tail = head;
while(front && front->next) {
front = front->next->next;
tail = tail->next;
if(front == tail) {
break;
}
}
if(front && front == tail) {
front = head;
while(front != tail && front != NULL && tail != NULL) {
front = front->next;
tail= tail->next;
}
return front;
} else {
return NULL;
}
}
};