Leetcode:142.环形链表 II

标题形貌:

给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 假如链表无环，则返回 null。
假如链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表现给定链表中的环，评测系统内部使用整数 pos 来表现链表尾毗连到链表中的位置（索引从 0 开始）。假如 pos 是 -1，则在该链表中没有环。留意：pos 不作为参数举行转达，仅仅是为了标识链表的现实情况。
不答应修改 链表。
示例 1：

1. <strong>输入：</strong>head = [3,2,0,-4], pos = 1
2. <strong>输出：</strong>返回索引为 1 的链表节点
3. <strong>解释：</strong>链表中有一个环，其尾部连接到第二个节点。

复制代码

示例 2：

1. <strong>输入：</strong>head = [1,2], pos = 0
2. <strong>输出：</strong>返回索引为 0 的链表节点
3. <strong>解释：</strong>链表中有一个环，其尾部连接到第一个节点。

复制代码

示例 3：

1. <strong>输入：</strong>head = [1], pos = -1
2. <strong>输出：</strong>返回 null
3. <strong>解释：</strong>链表中没有环。

复制代码

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
  
• -105 <= Node.val <= 105
  
• pos 的值为 -1 或者链表中的一个有用索引
  

进阶：你是否可以使用 O(1) 空间办理此题?
开始解题:

方法一:使用快慢指针(较难懂白,发起使用方法二)

Q1:怎么判断链表有没有环?
A1:可以定义两个指针,分别为快指针和慢指针,快指针一次走两步,慢指针一次一步,假如没有环,那么慢指针肯定可以到达链表尾部.假如有环,快指针肯定会重新和慢指针相遇,这里可以当作物理上的追击标题,以慢指针为参考系,快指针相称于一次移动一步.
Q2:怎么判断链表环的起始位置?(以下回复摘抄自代码随想录)
A2:假设重新结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才碰到slow指针， （y+z）为 一圈内节点的个数A。
由于fast指针是一步走两个节点，slow指针一步走一个节点， 以是 fast指针走过的节点数 = slow指针走过的节点数 * 2：
(x + y) * 2 = x + y + n (y + z)
双方消掉一个（x+y）: x + y = n (y + z)
由于要找环形的入口，那么要求的是x，由于x表现 头结点到 环形入口节点的的间隔。
以是要求x ，将x单独放在左面：x = n (y + z) - y ,
再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 留意这里n肯定是大于即是1的，由于 fast指针至少要多走一圈才气相遇slow指针。
这个公式阐明什么呢？
先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就碰到了 slow指针了。
当 n为1的时候，公式就化解为 x = z，
这就意味着，重新结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。
也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。 
让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。

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 *detectCycle(ListNode *head) {
12.         // 定义快慢指针
13.         ListNode* fast=head;
14.         ListNode* slow=head;
15.         // 这里使用fast指针判断,不能使用slow
16.         // 如果循环条件为slow!=NULL,那么如果链表长度为奇数,最后一次fast赋值会报错
17.         while(fast!=NULL && fast->next!=NULL){
18.             // 快指针一次两步,慢指针一次一步
19.             fast=fast->next->next;
20.             slow=slow->next;
21.             // 如果快慢指针相遇,代表链表存在环
22.             if(fast==slow){
23.                 // 定义meet指向相遇位置
24.                 ListNode* meet=fast;
25.                 // 定义另一指针从链表头出发
26.                 ListNode* index=head;
27.                 // 当两指针相遇,相遇位置就为链表环的位置
28.                 while(index!=meet){
29.                     index=index->next;
30.                     meet=meet->next;
31.                 }
32.                 return index;
33.             }
34.         }
35.         return NULL;
36.     }
37. };

复制代码

方法二:使用哈希表 

我们遍历链表中的每个节点，并将它记载下来；假如在哈希表中发现了类似指针,那么链表肯定有环,且该指针就为环的起始位置.

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 *detectCycle(ListNode *head) {
12.         // 定义哈希表记录出现的指针
13.         unordered_set<ListNode*> visited;
14.         // 使用cur来遍历链表
15.         ListNode* cur=head;
16.         while(cur!=NULL){
17.             // 如果哈希表中存在该指针
18.             if(visited.find(cur)!=visited.end()){
19.                 return cur;
20.             }
21.             // 把指针放入哈希表
22.             visited.insert(cur);
23.             // 更新指针
24.             cur=cur->next;
25.         }
26.         return NULL;
27.     }
28. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。