题目描述
给定一个链表的头节点 head
,返回链表开始入环的第一个节点。 如果链表无环,则返回 null
。
如果链表中有某个节点,可以通过连续跟踪 next
指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 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, 104]
内 -105 <= Node.val <= 105
pos
的值为-1
或者链表中的一个有效索引
进阶:你是否可以使用 O(1)
空间解决此题?
解法一
思路:
采用哈希表,依次遍历所有的节点,若当前节点在哈希表中出现,那么返回该节点。
/*** 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 || head.next == null) return null;Set<ListNode> set = new HashSet<>();ListNode p=head;while (p!=null) {if(set.contains(p)) return p;set.add(p);p = p.next;}return null;}
}
解法二
思路:
采用快慢指针的方法,当快慢指针相遇的时候,那么现在肯定在环内,此时再设置一个指针,从头指针开始,依次向后移动,同时,slow指针也向后移动。若他们相遇则就是入环点。
证明:
代码:
/*** 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) {ListNode slow = head;ListNode fast = head;ListNode ptr = head;boolean flag = false;while (fast != null && fast.next != null) {slow = slow.next;fast = fast.next.next;if (slow == fast){flag=true;break;}}if (!flag)return null;while(true){if(ptr == slow)return slow;slow = slow.next;ptr = ptr.next;}}
}