环形链表

问题陈述

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

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

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

方法一：（哈希表）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution{
    public ListNode detectCycle(ListNode head){
        Set<ListNode> visited=new HashSet<>();
        ListNode node=head;
        while(node!=null){
            if(visited.contains(node)){
                return node;
            }
            visited.add(node);
            node=node.next;
        }
        return null;
    }
}

方法二：（双指针）

这类链表题目一般都是使用双指针法解决的，例如寻找距离尾部第K个节点、寻找环入口、寻找公共尾部入口等。

设置快慢指针，构造两次相遇，第一次相遇后快指针回到起点，然后两个指针以相同的步调前进。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution{
    public ListNode detectCycle(ListNode head){
        ListNode fast=head;
        ListNode slow=head;
        while(true){
            if(fast==null||fast.next==null) return null;
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow) break;
        }
        fast=head;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast;
 
    }
}