LeetCode Linked List Cycle II 和I 通用算法和优化算法
Linked List Cycle II
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?
和问题一Linked List Cycle几乎一样。如果用我的之前的解法的话，可以很小修改就可以实现这道算法了。但是如果问题一用优化了的解法的话，那么就不适用于这里了。下面是我给出的解法，可以看得出，这里需要修改很小地方就可以了。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:bool find(ListNode *head, ListNode *testpNode){ListNode *p = head;while (p != testpNode->next){if(p == testpNode)return false;p = p->next;}return true;}ListNode *detectCycle(ListNode *head) {// IMPORTANT: Please reset any member data you declared, as// the same Solution instance will be reused for each test case.if(head == NULL)return false;ListNode *cur = head;while(cur != NULL){if(find(head, cur))return cur->next;cur = cur->next;}return NULL;}};然后转一下下面那位朋友的博客，他的解法很优化，不过只适合第一个LeetCode Linked List Cycle问题，而不适合这里。值得学习学习，一起贴在这里了。
http://blog.csdn.net/doc_sgl/article/details/13614853
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: bool hasCycle(ListNode *head) { // IMPORTANT: Please reset any member data you declared, as // the same Solution instance will be reused for each test case. ListNode* pfast = head;ListNode* pslow = head;do{if(pfast!=NULL)pfast=pfast->next;if(pfast!=NULL)pfast=pfast->next;if(pfast==NULL)return false;pslow = pslow->next;}while(pfast != pslow);return true; }};