题目:有一个单向链表, 链表中有可能出现”环”, 就像下图这样.那么, 如何用程序来判断该链表是否为有环链表呢?

image-20210425205713779.png
2.思路扩展:
环形跑道追及问题: 男生和女生从同一起点起跑, 直到两人再次相遇
image-20210426193707844.png
3.解法:
定义两个指针p1, p2, p1每次移动1个单位, p2每次移动2个单位, 并且同时从头节点出发, 如果p1和p2再次相遇, 则证明链表有环, 反之无环.

4.代码:

  1. package com.xiaoxuanfeng.letcode;
  3. public class TheRingOfLinkedList {
  4.     // 1.定义节点
  5.     private static class Node {
  6.         int data; // 当前节点的值
  7.         Node next; // 指向下一节点
  9.         Node(int data) {
  10.             this.data = data;
  11.         }
  12.     }
  14.     // 2.判断是否有环
  15.     public static boolean isCycle(Node head) {
  16.         // 定义p1,, p2, 让它们从head同时出发
  17.         Node p1 = head;
  18.         Node p2 = head;
  19.         while (p2 != null && p2.next !=null) {
  20.             p1 = p1.next; // p1移动1个单位
  21.             p2 = p2.next.next; //  p2移动2个单位
  22.             if (p1 == p2) {
  23.                 return true;
  24.             }
  25.         }
  26.         return false;
  27.     }
  29.     // 3.调用主函数进行测试
  30.     public static void main(String[] args) {
  31.         // 创建链表
  32.         Node node1 = new Node(1);
  33.         Node node2 = new Node(2);
  34.         Node node3 = new Node(3);
  35.         Node node4 = new Node(4);
  37.         // 把节点连走来
  38.         node1.next = node2;
  39.         node2.next = node3;
  40.         node3.next = node4;
  41.         node4.next = null;
  43.         // 打印结果
  44.         System.out.println(isCycle(node1));
  45.     }
  47. }