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

解法1：

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

解法2：

单循环遍历，遍历新节点时查找对象中是否存有此节点，如何有，则有环，如果没有则存入对象，时间复杂度 O(n)，空间复杂度 O(n)

解法3：

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

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

代码如下：

1      /**
2       * @param {*} head 链表头节点
3       * @description 判断链表是否有环
4       */
5       function isCycle(head:LinkNodeType | null):boolean {
6          let p1 = head;
7          let p2 = head;
8          while(p2!==null && p2.next !== null && p1 !== null) {
9              p2 = p2.next.next;
10              p1 = p1.next;
11              if(p2 === p1) {
12                  return true
13              }
14          }
15          return false
16      };
17      
18      
19      function main() {
20          let node1 = new LinkNode(5)
21          let node2 = new LinkNode(3)
22          let node3 = new LinkNode(7)
23          let node4 = new LinkNode(2)
24          let node5 = new LinkNode(6)
25          let node6 = new LinkNode(8)
26          let node7 = new LinkNode(1)
27      
28      
29          node1.next = node2;
30          node2.next = node3;
31          node3.next = node4;
32          node4.next = node5;
33          node5.next = node6;
34          node6.next = node7;
35          node7.next = node5;
36      
37      
38          console.log(isCycle(node1))
39      }
40      
41      
42      main()
43

扩展：

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

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

代码如下：

1    /**
2     * @param {(LinkNodeType | null)} head 
3     * @returns {(boolean|number)}
4     * @description 判断链表是否有环，如何有环 求出环长
5     */
6    function cycleLength(head: LinkNodeType | null):boolean|number {
7        let p1 = head;
8        let p2 = head;
9        let isFirst = true;
10        let length = 0
11        while(p1 !== null&& p2 !== null && p2.next !== null) {
12            p2 = p2.next.next;
13            p1 = p1.next;
14            if(!isFirst) {
15                length ++
16            }
17            if(p2 == p1 && !isFirst)  {
18                return length
19            }
20            if(p2 == p1) {
21                isFirst = false
22            }
23        }
24        return false
25    }
26

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，则相遇点即是 入环点

代码如下：

1      /**
2       * @param {*} head 链表头节点
3       * @description 判断链表是否有环
4       */
5       function isCycle(head:LinkNodeType | null):boolean | LinkNode {
6          let p1 = head;
7          let p2 = head;
8          while(p2!==null && p2.next !== null && p1 !== null) {
9              p2 = p2.next.next;
10              p1 = p1.next;
11              if(p2 === p1) {
12                  return p1 as LinkNode
13              }
14          }
15          return false
16      };
17      
18      
19      /**
20       * @param {*} firstDot 首次相遇点
21       * @returns 入环点
22       */
23      function cycleDot(firstDot:LinkNode,headDot:LinkNode):LinkNode {
24          let p1 = firstDot;
25          let p2 = headDot;
26          while(p1 !== p2) {
27              p1 = p1.next as LinkNode;
28              p2 = p2.next as LinkNode;
29          }
30          return p1
31      }
32      
33      
34      function main() {
35          let node1 = new LinkNode(5)
36          let node2 = new LinkNode(3)
37          let node3 = new LinkNode(7)
38          let node4 = new LinkNode(2)
39          let node5 = new LinkNode(6)
40          let node6 = new LinkNode(8)
41          let node7 = new LinkNode(1)
42      
43      
44          node1.next = node2;
45          node2.next = node3;
46          node3.next = node4;
47          node4.next = node5;
48          node5.next = node6;
49          node6.next = node7;
50          node7.next = node4;
51          let firstNode = isCycle(node1)
52          if(firstNode){
53              console.log(cycleDot(firstNode as LinkNode, node1))
54          }
55      }
56

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