解法参考:http://blogread.cn/it/article/2452?f=hot1
先判断有没有环,有环的话,设两个指针,一个指针在head,另一个指针在相遇的点,两个指针同时往前走,则这两个指针相遇的点就是环的开始节点。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *detectCycle(ListNode *head) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. ListNode *cross = findCross(head); ListNode *tmp = head; if(cross != NULL){ while(tmp != cross){ cross = cross->next; tmp = tmp->next; } } return cross; } ListNode *findCross(ListNode *head){ if(head == NULL || head->next == NULL) return NULL; ListNode *cross = NULL, *one = head->next, *two = head->next->next; while(one != NULL && two != NULL){ if(one == two){ cross = one; return cross; } if(two->next == NULL) return cross; one = one->next; two = two->next->next; } return cross; } };