判断单向链表是否有环及求环入口

不念不忘少年蓝@ 2023-06-17 04:57 38阅读 0赞

最简单的方法就是遍历链表，并用一个容器保存遍历过的链表节点，当出现重复节点时，即可得出链表存在闭环。代码如下：

public boolean isHavRing() {
        List<Node> nodes = new ArrayList<>();
        Node node = this;
        while (node != null && !nodes.contains(node)) {
          nodes.add(node);
          node = node.next;
        }
        return node != null;
      }

链表实现请移步码云：[链表实现][Link 1]

下面从通过数学算法判断单向链表是否有环及求环入口，这也是面试中考究的知识点。

判断单向链表是否有环方法就是通过一组快、慢指针去遍历链表，快指针每次向前走2步，慢指针每次走1步，如果链表存在环，最终两个指针会相遇。代码如下：

package com.spring.component.leetcode.difficult;
    
    import com.spring.component.link.LinkFactory;
    import com.spring.component.link.Node;
    import com.spring.component.link.SingleNode;
    
    /**
     * 判断单向链表是否有环及求环入口
     *
     * @ClassName: com.spring.component.leetcode.difficult.LinkHaveRing
     * @Description: 该类的功能描述
     * @version: v1.0.0
     * @author: 52879
     * @date: 2019/11/22 20:04
     */
    public class LinkHaveRing {
    
      /**
       * 判断单向链表是否有环 一个快指针，一个慢指针，快指针每次向前2步，慢指针每次向前1步；如果有闭环，两个指针最终会指向同一个节点
       * 
       * @param singleNode
       * @return
       */
      public static boolean isHaveRing(SingleNode singleNode) {
        return runMeet(singleNode, singleNode, true) != null;
      }
    
      /**
       * 计算闭环切入节点
       * 1、快、慢指针都从head开始向前，快指针每次向前2步，慢指针每次向前1步
       * 2、如果有闭环，两指针会相遇；相遇后，快指针重新从head开始向前，每次1步，
       *    慢指针从相遇点开始向前，每次1步，再次相遇点就是闭环切入点
       * 
       * @param singleNode
       * @return
       */
      public static Node getRingCutPoint(SingleNode singleNode) {
        Node mettNode = runMeet(singleNode, singleNode, true);
        // 相遇后，快指针从head开始移动，慢指针从相遇点移动，再次相遇点便是闭环切入点
        return runMeet(singleNode, mettNode, false);
      }
    
      public static Node runMeet(Node fastSingleNode, Node slowSingleNode,
          boolean isFast) {
        Node fastNode = fastSingleNode.getNext();
        if (fastNode == null) {
          // 快指针指向了null
          return null;
        }
        if (isFast) {
          fastNode = fastNode.getNext();
        }
        Node slowNode = slowSingleNode.getNext();
        while (fastNode != slowNode) {
          if (isFast) {
            fastNode = fastNode.getNext();
          }
          if (fastNode == null) {
            return null;
          }
          fastNode = fastNode.getNext();
          slowNode = slowNode.getNext();
        }
        return fastNode;
      }
    
      public static void main(String[] args) {
        SingleNode singleNode = LinkFactory.buildSingleNode(1, 2, 3, 4, 5);
        // 存在闭环链表
        singleNode.getNext().getNext().getNext().getNext().setNext(singleNode.getNext());
        System.out.println(isHaveRing(singleNode));
        System.out.println(getRingCutPoint(singleNode).toNodeString());
      }
    }

数学证明有兴趣的同学请点这里：[大婶子判断单向链表是否有环及求环入口数学证明][Link 2]

[Link 1]: https://gitee.com/jlzl/componet/tree/master/component-base/src/main/java/com/spring/component/link
[Link 2]: https://zhuanlan.zhihu.com/p/33663488