环形链表找入口节点（Python and C++解法）
2021-04-29 21:26
标签：另一个 cycle 修改 || 节点 node ntc 允许 指针 给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。 说明：不允许修改给定的链表。 来源：力扣（LeetCode） 分三个环节完成： 第一环节判断是否有环，使用快慢指针进行操作； 第二环节计算环中节点的数量，如果有环，相遇点一定在环内，计算再次走到相遇点经过的结点数即可； 第三环节找入口节点，在已知环的节点数量countCycle的前提下，使一个指针从头先走countCycle步，然后使另一个指针从头同步开始走，它们的相遇点就是环的入口点，因为nodeA先走countCycle步后离入口点的距离与此时B离入口点的距离相同。 环形链表找入口节点（Python and C++解法） 标签：另一个 cycle 修改 || 节点 node ntc 允许 指针 原文地址：https://www.cnblogs.com/kongzimengzixiaozhuzi/p/13231195.html题目：
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii思路：
Python解法：
1 class ListNode:
2 def __init__(self, x):
3 self.val = x
4 self.next = None
5
6 class Solution:
7 def detectCycle(self, head: ListNode) -> ListNode:
8 slow = head
9 fast = head
10 while fast and fast.next:
11 slow = slow.next
12 fast = fast.next.next
13 if fast == slow:
14 meetNode = fast # 相遇点
15 break # 找到相遇点后跳出循环
16 if fast == None or fast.next == None:
17 return None # 链表没有环
18
19 slow = meetNode.next
20 countCycle = 1 # 计算环的节点数量
21 while slow != meetNode:
22 countCycle += 1
23 slow = slow.next
24
25 nodeA = head
26 nodeB = head
27 while countCycle:
28 nodeA = nodeA.next
29 countCycle -= 1
30 while nodeA != nodeB: # 再次相遇节点就是入口节点
31 nodeA = nodeA.next
32 nodeB = nodeB.next
33 return nodeA
C++解法：
1 struct ListNode {
2 int val;
3 ListNode *next;
4 ListNode(int x) : val(x), next(NULL) {}
5 };
6
7 class Solution {
8 public:
9 ListNode *detectCycle(ListNode *head) {
10 // 判断是否有环
11 ListNode *slow = head;
12 ListNode *fast = head;
13 ListNode *meetNode;
14 while (fast && fast -> next) {
15 slow = slow -> next;
16 fast = fast -> next -> next;
17 if (fast == slow) {
18 meetNode = fast;
19 break;
20 }
21 }
22 if (fast == NULL || fast -> next == NULL)
23 return NULL;
24 // 计算环中节点的数量
25 int countCycle = 1;
26 slow = meetNode -> next;
27 while (slow != meetNode) {
28 slow = slow -> next;
29 countCycle += 1;
30 }
31
32 // 找入口节点
33 ListNode *nodeA = head;
34 ListNode *nodeB = head;
35 while (countCycle--)
36 nodeA = nodeA -> next;
37 while (nodeA != nodeB) {
38 nodeA = nodeA -> next;
39 nodeB = nodeB -> next;
40 }
41 return nodeA;
42 }
43 };
上一篇：c#代码规范
文章标题：环形链表找入口节点（Python and C++解法）
文章链接：http://soscw.com/index.php/essay/80192.html