如何判断链表有环

如果判断链表有环？如下链表

解法1：

双循环遍历，每次遍历新的节点，就往前查找此节点是否存在过，时间复杂度 O(n2)，空间复杂度O(1)

解法2：

但循环遍历，没遍历一个节点，就存入对象，遍历新节点是查找对象中是否存有此节点，时间复杂度 O(n)，空间复杂度 O(n)

解法3：

设置两个指针，p1、p2，指向节点头，接下来每次让 p1 前进一个节点，p2 往前两个节点，若链表有环，则p2、p1则会重合，即指向同一节点

时间复杂度O(n)，空间复杂度O(1)

代码如下：

      /**
       * @param {*} head 链表头节点
       * @description 判断链表是否有环
       */
       function isCycle(head:LinkNodeType | null):boolean {
          let p1 = head;
          let p2 = head;
          while(p2!==null && p2.next !== null && p1 !== null) {
              p2 = p2.next.next;
              p1 = p1.next;
              if(p2 === p1) {
                  return true
              }
          }
          return false
      };
      
      
      function main() {
          let node1 = new LinkNode(5)
          let node2 = new LinkNode(3)
          let node3 = new LinkNode(7)
          let node4 = new LinkNode(2)
          let node5 = new LinkNode(6)
          let node6 = new LinkNode(8)
          let node7 = new LinkNode(1)
      
      
          node1.next = node2;
          node2.next = node3;
          node3.next = node4;
          node4.next = node5;
          node5.next = node6;
          node6.next = node7;
          node7.next = node5;
      
      
          console.log(isCycle(node1))
      }
      
      
      main()
复制代码

扩展：

1. 如果链表有环，求出环的长度

解法：当两个指针第一次相遇之后，证明链表有环，此时让指针继续往前走，直到第二次相遇，此时，快的指针比慢的指针多走了一圈

代码如下：

    /**
     * @param {(LinkNodeType | null)} head 
     * @returns {(boolean|number)}
     * @description 判断链表是否有环，如何有环 求出环长
     */
    function cycleLength(head: LinkNodeType | null):boolean|number {
        let p1 = head;
        let p2 = head;
        let isFirst = true;
        let length = 0
        while(p1 !== null&& p2 !== null && p2.next !== null) {
            p2 = p2.next.next;
            p1 = p1.next;
            if(!isFirst) {
                length ++
            }
            if(p2 == p1 && !isFirst)  {
                return length
            }
            if(p2 == p1) {
                isFirst = false
            }
        }
        return false
    }
复制代码

2. 如果链表有环，求出入环点

解：

如下示意图

p1 指针走的距离为 D + S1

p1 指针走的距离为 D + S1 + S2 + S1 = D + S2 + 2S1

又因为 p2 指针速度为 2，p1 指针速度为 1 所以

D + S2 + 2S1 = 2(D + S1)

D + S2 + 2S1 = 2D + 2S1

D + S2 = 2D

D = S2

所以，当两个节点第一次相遇时，得到该节点，设置两个指针 p1 p2 分别放到链表头，和相遇节点，分别依次走 1，则相遇点即是 入环点

代码如下：

      /**
       * @param {*} head 链表头节点
       * @description 判断链表是否有环
       */
       function isCycle(head:LinkNodeType | null):boolean | LinkNode {
          let p1 = head;
          let p2 = head;
          while(p2!==null && p2.next !== null && p1 !== null) {
              p2 = p2.next.next;
              p1 = p1.next;
              if(p2 === p1) {
                  return p1 as LinkNode
              }
          }
          return false
      };
      
      
      /**
       * @param {*} firstDot 首次相遇点
       * @returns 入环点
       */
      function cycleDot(firstDot:LinkNode,headDot:LinkNode):LinkNode {
          let p1 = firstDot;
          let p2 = headDot;
          while(p1 !== p2) {
              p1 = p1.next as LinkNode;
              p2 = p2.next as LinkNode;
          }
          return p1
      }
      
      
      function main() {
          let node1 = new LinkNode(5)
          let node2 = new LinkNode(3)
          let node3 = new LinkNode(7)
          let node4 = new LinkNode(2)
          let node5 = new LinkNode(6)
          let node6 = new LinkNode(8)
          let node7 = new LinkNode(1)
      
      
          node1.next = node2;
          node2.next = node3;
          node3.next = node4;
          node4.next = node5;
          node5.next = node6;
          node6.next = node7;
          node7.next = node4;
          let firstNode = isCycle(node1)
          if(firstNode){
              console.log(cycleDot(firstNode as LinkNode, node1))
          }
      }
复制代码

摘要总结自: 漫画算法 小灰的算法之旅