链表中环的入口节点

题目描述

对于一个给定的链表，返回环的入口节点，如果没有环，返回null

拓展：

你能给出不利用额外空间的解法么？

/** * 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) { if(head==NULL) return NULL; ListNode* fast=head; ListNode* slow=head; while(fast!=NULL && fast->next!=NULL){ slow = slow->next; fast=fast->next->next; if(slow==fast){ ListNode*cur = head; while(cur != fast){ cur = cur->next; fast = fast->next; } return cur; } } return NULL; } };