java单链表是否存在环及环的入口节点

Love The Way You Lie 2023-06-08 06:51 4阅读 0赞

### 思路： ###

**是否存在环：快慢指针来判断是否存在环，快指针每次走两步，慢指针每次走一步，快慢指针相遇，即存在环**

**环入口节点：快慢指针相遇后，慢指针回到头节点，快指针每次走一步，相遇的节点即为入口节点，这里也可以顺便算出位置**

###  代码及注释 ###

public class LinkListDemo {
    
      public static void main(String[] args) {
    
          // 构造四个节点
          Node head = new Node();
          head.value = 1;
          Node next = new Node();
          next.value = 2;
          Node third = new Node();
          third.value = 3;
          Node forth = new Node();
          forth.value = 4;
          Node fifth = new Node();
          fifth.value = 5;
    
          head.next=next;
          next.next=third;
          third.next=forth;
          forth.next=fifth;
          fifth.next=next;
          // 构造四个节点结束
    
          System.out.println(isExistsCircle(head));
          System.out.println(indexOfExistsCircle(head).value);
    
      }
    
      /**
       * 判断链表是否存在环
       * @param head
       * @return
       */
      public static boolean isExistsCircle(Node head){
          Node slow = head;
          Node fast = head;
    
          // 一个节点的情况
          if(head.next == head ){
            return true;
          }
          while(fast.next.next != null ){
                slow = slow.next;
                fast = fast.next.next;
                if(slow == fast){
                  return  true;
                }
          }
          return false;
      }
    
    
      /**
       * 寻找环的入口节点
       * @param head
       * @return
       */
      static Node indexOfExistsCircle(Node head){
        Node slow = head; // 慢指针
        Node fast = head; // 块指针
    
        // 一个节点的情况
        if(head.next == head ){
          return head;
        }
    
        while(fast.next.next != null ){
          slow = slow.next;
          fast = fast.next.next;
          if(slow == fast){
            break;
          }
        }
        slow = head;
        while(fast != slow){
          slow = slow.next;
          fast = fast.next;
        }
        return slow;
    
      }
    
    }
    
    class Node{
       int value;
       Node next;
    }

运行截图：

![20191017161631765.png][]

[20191017161631765.png]: /images/20230531/61ce07a197b548b08897beed90b27730.png