方法一

快慢指针 寻找环
第一个指针 一次走1, 快指针一次走2
易得第一次相遇时 慢指针一定没有走完一圈,
故慢指针的 路程为X+Y
则快指针路径 为 2X+2Y
我们把慢指针回退到b
那么快指针距离B路程为 y 就是说 快指针距离b点路程为y时路程为2x
我们还可以直到2x+y就是b点
第一次相遇的点处为X+Y
我们把快指针放到a点 以1的速度 再次和慢指针相遇即为b点

  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode(int x) : val(x), next(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     ListNode *entryNodeOfLoop(ListNode *head) {
  12.         if(!head || !head->next) return 0;
  13.         ListNode *first = head,  *second = head;
  15.         while(1) {
  16.             if(second && second->next) 
  17.                 second = second->next;
  18.             else 
  19.                 return 0;
  21.             first = first->next;
  22.             second = second->next;
  25.             if(first == second){
  26.                 first = head;
  27.                 while(first != second) {
  28.                     first = first->next;
  29.                     second = second->next;
  30.                 }
  31.                 return first;
  32.             }
  33.         }
  34.         return 0;
  35.     }
  36. };

方法二

给每一个地址一个哈希值,第一个出现两次的地址就环,否则遍历完链表自动退出,需要O(n)的空间

  1. class Solution 
  2. {
  3. public:
  4.     unordered_map<ListNode*,int> h;
  5.     ListNode *entryNodeOfLoop(ListNode *head) 
  6.     {
  7.         int id = 1;
  8.         for(auto i = head;i;i = i->next,id++)
  9.         {
  10.             if(h[i] != 0)
  11.             {
  12.                 return i;
  13.             }
  14.             else
  15.             {
  16.                 h[i] = id;
  17.             }
  18.         }
  19.         return NULL;
  20.     }
  21. };