常见面试题：链表3-判断链表是否有环以及环入口节点

素颜马尾好姑娘i 2023-10-04 18:42 55阅读 0赞

### 常见面试题3：链表-判断链表是否有环以及环入口节点 ###

#### 内容目录 ####

*   *  常见面试题3：链表-判断链表是否有环以及环入口节点
     *   *  一、判断链表是否有环
         *   *  1.解法1：使用列表
             *  2.解法2：快慢指针
         *  二、链表环入口节点
         *   *  解法1：使用列表
             *  解法2：快慢指针

> 链表可以分为单向链表、双向链表、环形链表。对于环形链表，如果我们事前不知道，遍历的时候就会出现死循环，导致程序失败。那么如何判断链表是否有环以及环入口节点也是面试中经常问到的

#### 一、判断链表是否有环 ####

能想到的解法大概有两种，第一种就是把每次遍历的结果放到一个链表中，每次遍历的时候判断该链表中是否有该节点如果有就是有环，否则就是没有

第二种就是采用快慢指针的方法，维护两个指针，快指针每次向前移动两个位置，慢指针移动一个，如果快指针和慢指针指向节点一样，就说明有环

##### 1.解法1：使用列表 #####

public boolean hasCycle(ListNode head) {
        
      if(head == null) return false;
      ArrayList<ListNode> list = new ArrayList<>();
      while(head.next != null){
        
        if(list.contains(head)){
        
          return true;
        }
        list.add(head);
        head = head.next;
        }
      return false;
    }

##### 2.解法2：快慢指针 #####

public boolean hasCycle(ListNode head) {
        
      if(head == null) return false;
      ListNode fast = head, slow = head;
      while (fast.next != null && fast.next.next != null) {
        
          fast = fast.next.next;
          slow = slow.next;
          if(fast == slow) return true;
      } 
      return false;
    }

#### 二、链表环入口节点 ####

和上述的一样，也有两种方法，第一种就是列表，当判断在列表中第一次存在时，就证明这个节点为入口节点

快慢指针就相对难想到一点，我们可以想到，当快指针追上慢指针时候，证明有环，同时慢指针移动的节点数是慢节点的两倍，所以，这时将快指针移动到head节点，与慢指针保持同速，每次移动一个节点，那么下一次相遇，就是环的入口节点

**第一次相遇**  
![在这里插入图片描述][6eb39d97d3424e389a2d8f2d497b3354.png]

**第二次相遇：**  
![在这里插入图片描述][32b9e4e1cd5443298d70d2829fc5e30f.png]

##### 解法1：使用列表 #####

public ListNode EntryNodeOfLoop(ListNode pHead) {
        
      ArrayList<ListNode> list = new ArrayList<>();
      while(pHead.next != null){
        
        if(list.contains(pHead)) return pHead;
        list.add(pHead);
        pHead = pHead.next;
      }
      return null;
    }

##### 解法2：快慢指针 #####

public ListNode EntryNodeOfLoop(ListNode pHead) {
        
      if(pHead == null) return null;
      ListNode slow = pHead, fast = pHead;
      // 第一次相遇
      while(fast.next != null && fast.next.next != null){
        
        fast = fast.next.next;
        slow = slow.next;
        if(fast == slow) break;
      }
      if(fast.next == null || fast.next.next == null) return null;
      fast = pHead;
      // 第二次相遇
      while(fast != slow){
        
        fast = fast.next;
        slow = slow.next;
      }
      return fast;
    }

[6eb39d97d3424e389a2d8f2d497b3354.png]: https://img-blog.csdnimg.cn/6eb39d97d3424e389a2d8f2d497b3354.png
[32b9e4e1cd5443298d70d2829fc5e30f.png]: https://img-blog.csdnimg.cn/32b9e4e1cd5443298d70d2829fc5e30f.png