【LeetCode 142】环形链表 II

【LeetCode 142】环形链表 II

题目描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1输出：tail connects to node index 1

示例 2：

输入：head = [1,2], pos = 0输出：tail connects to node index 0

示例 3：

输入：head = [1], pos = -1

进阶： 你是否可以不用额外空间解决此题？

解题思路

和之前的144题：​​【LeetCode 141】环形链表​​，原理一样，都是设置一个flag，只是返回值不一样，最后指向的是有flag 的节点，所以直接返回head即可。

上述方法需要开辟O(n)的储存空间来储存标记信息，那我们尝试用快慢指针来解决这个问题：

我们设置两个指针，快指针每次走两个节点，慢指针每次走一个节点，如果存在环，那么两个指针一定相遇。等快慢指针相遇之后，我们在用另一个指针，去寻找他们相遇的位置就可以了。

代码实现

第一种方法：

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} head * @return {ListNode} */var detectCycle = function(head) { while(head){ if(head.flag){ return head }else{ head.flag = true head = head.next } } return null};

第二种方法：

/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} head * @return {ListNode} */var detectCycle = function(head) { let fast = head let slow = head let cur = head while(fast && fast.next && fast.next.next){ slow = slow.next fast = fast.next.next if(fast == slow){ while(cur!=slow){ cur = cur.next slow = slow.next } return slow } } return null};

提交结果

第一种方法：

第二种方法：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。