环形链表

链表

判断链表是否有环

image-20230421224715837

方式一(哈希表)

使用哈希表

  • 从头到尾遍历链表
  • 依次塞进哈希表，在塞进哈希表之前，先检查表中是否存在该节点
  • 存在，就说明有环
  • 链表遍历到尾部，也没有发现，就说明该链表没有环

代码实现过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
      HashSet<ListNode> set = new HashSet();
      ListNode node = head;
      while(node != null){
          if(!set.add(node)){
			return true;
          }
          node = node.next;
      }
      return false;
    }
}

方式二(快慢指针)

使用快慢指针

  1. 设置一个快指针每次走两步，一个慢指针，一次走一步
  2. 若快指针走到空，说明链表无环
  3. 如果有环，快慢指针会在环里面相交
  4. 相交时刻，将快指针置为头节点，此刻开始，快慢指针每次都是走一步
  5. 下次相遇时刻就是环的入口

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * 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 fast = head;
        ListNode slow = head;
        
        while(fast!=null){
          slow = slow.next;
          
          if(fast.next!=null){
            fast = fast.next.next;
          }else{
            return null;
          }
          
          if(fast == slow){
            fast = head;
            while(fast != slow){
              fast = fast.next;
              slow = slow.next;
            }
            return fast;
          }
        }
        return fast;
    }
}