带环链表 II-LintCode,给定一个链表,如果链表中存在环,则返回到链表中环的起始节点的值,如果没有环,返回null。
样例
给出 -21->10->4->5, tail connects to node index 1,返回10
#ifndef C103_H #define C103_H #includeusing namespace std; 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 ListNode *fast = head, *slow = head; while (fast&&fast->next) { slow = slow->next; fast = fast->next->next; if (fast == slow) break; } if (fast==NULL || fast->next==NULL) return NULL; slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } }; #endif