图书馆网站的建设的重要性,东莞知名网站建设,昭平县建设局网站,餐厅类网站模板题目链接 Leetcode.剑指 Offer II 022 链表中环的入口节点 mid 题目描述
给定一个链表#xff0c;返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next指针进入环的第一个节点为环的入口节点。如果链表无环#xff0c;则返回 null。
为了表示给定链表中的环#…题目链接 Leetcode.剑指 Offer II 022 链表中环的入口节点 mid 题目描述
给定一个链表返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next指针进入环的第一个节点为环的入口节点。如果链表无环则返回 null。
为了表示给定链表中的环我们使用整数 pos来表示链表尾连接到链表中的位置索引从 0开始。 如果 pos是 -1则在该链表中没有环。注意pos仅仅是用于标识环的情况并不会作为参数传递到函数中。
说明不允许修改给定的链表。
示例 1 输入head [3,2,0,-4], pos 1 输出返回索引为 1 的链表节点 解释链表中有一个环其尾部连接到第二个节点。 示例 2 输入head [1,2], pos 0 输出返回索引为 0 的链表节点 解释链表中有一个环其尾部连接到第一个节点。 示例 3 输入head [1], pos -1 输出返回 null 解释链表中没有环。 提示
链表中节点的数目范围在范围 [0,1040, 10^40,104] 内−105Node.val105-10^5 Node.val 10^5−105Node.val105pos的值为 -1或者链表中的一个有效索引
分析快慢指针
我们用两个指针 fast和slow初始都指向 headfast每次走两步slow每次走一步。
如果链表存在环那么 fast和 slow一定会在环中相遇。 因为fast比slow要快1步所以当 slow走过的距离为 x y到达相遇点时fast其实已经在环里转了若干圈了这里假设是 n圈。
所以 fast走过的路程为 xn∗(yz)yx n * (y z) yxn∗(yz)y
又因为 fast走过的路程 应该是 两倍slow走过的路程即 xn∗(yz)y2∗(xy)x n * (y z) y 2 * (x y)xn∗(yz)y2∗(xy)
化简得 x(n−1)∗(yz)zx (n - 1) * (y z) zx(n−1)∗(yz)z即从相遇点走 z的路程再走若干圈就是 x的路程。我们只需要走 0 圈即可即 xzx zxz。
当 fast和 slow相遇时让 fast重新指向头节点 headfast和slow同时移动当他们再次相遇时的点就是环的起点。
时间复杂度 O(n)O(n)O(n)
C代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head nullptr) return nullptr;ListNode *fast head , *slow head;while(fast fast-next){slow slow-next;fast fast-next-next;//两者相遇if(slow fast){fast head;while(slow ! fast){slow slow-next;fast fast-next;}return slow;}}return nullptr;}
};
Java代码
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(head null) return null;ListNode fast head;ListNode slow head;//fast 或 fast.next 为 null , 说明链表没有环while(fast ! null fast.next ! null){slow slow.next;fast fast.next.next;//快慢指针相遇了,fast 重新回到头节点 head,快慢指针再同时移动if(slow fast){fast head;while(fast ! slow){fast fast.next;slow slow.next;}return fast;}}return null;}
}
