WHCSRL 技术网

[LeetCode]Link List Cycle II_weixin

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?

思考:第一步:设环长为len,快慢指针q、p相遇时,q比p多走了k*len。
        第二部:p先走k*len步,p,q一起走每次一步,相遇时p比q多走了一个环距离,此时q就是环开始结点。

        通过分析AC的感觉真好!

  1. class Solution {
  2. public:
  3. ListNode *detectCycle(ListNode *head) {
  4. // IMPORTANT: Please reset any member data you declared, as
  5. // the same Solution instance will be reused for each test case.
  6. if(!head||!head->next) return NULL;
  7. ListNode *p=head;int countP=0;
  8. ListNode *q=p->next;int countQ=1;
  9. bool flag=false;
  10. int len=0;
  11. while(q&&q->next)
  12. {
  13. if(p==q)
  14. {
  15. len=countQ-countP;
  16. flag=true;
  17. break;
  18. }
  19. else
  20. {
  21. q=q->next->next;
  22. p=p->next;
  23. countP+=1;
  24. countQ+=2;
  25. }
  26. }
  27. if(flag)
  28. {
  29. p=head;
  30. q=head;
  31. while(len--)
  32. {
  33. p=p->next;
  34. }
  35. while(p!=q)
  36. {
  37. p=p->next;
  38. q=q->next;
  39. }
  40. return p;
  41. }
  42. else return NULL;
  43. }
  44. };

  

 

转载于:https://www.cnblogs.com/Rosanna/p/3426608.html

文章知识点与官方知识档案匹配,可进一步学习相关知识
推荐阅读