What if the list has a ring? The following list

Method 1:

Double cycle traversal. Each time a new node is traversed, whether the node has existed is searched ahead. Time complexity O(n2), space complexity O(1)

Method 2:

However, the loop traverses, without traversing a node, the object is saved. Traversing a new node is to find whether the node exists in the object. The time complexity is O(n), the space complexity is O(n).

Method 3:

Set two Pointers, P1 and p2, and nod at the node. Then move P1 forward one node at a time, and P2 forward two nodes at a time. If the list has a ring, p2 and P1 will overlap, that is, point to the same node

Time complexity O(n), space complexity O(1)

The code is as follows:

/ * * * @ param {*} head head node * @ * / function with a loop description to judge whether the list 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()Copy the code

Extension:

1. If the list has rings, find the length of the rings

Solution: When two Pointers meet for the first time and prove that the linked list has a ring, let the pointer continue to move until the second time, at this point, the fast pointer has made one more turn than the slow pointer

The code is as follows:

/ * * * @ param {(LinkNodeType | null)} head * @ returns {(Boolean | number)} * @ the description to determine whether a linked list has a ring, How long ring and ring * / 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 }Copy the code

2. If the list has rings, find the entry and exit points

Solution:

As shown below

The distance traveled by the p1 pointer is D + S1

The distance traveled by p1 pointer is D + S1 + S2 + S1 = D + S2 + 2S1

And the speed of p2 is 2, and the speed of P1 is 1

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

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

D + S2 = 2D

D = S2

Therefore, when the two nodes meet for the first time, the node is obtained. Set two Pointers P1 and P2 to the head of the linked list respectively, and the encounter node, and go 1 respectively. Then the encounter point is the entry point of the loop

The code is as follows:

/ * * * @ param {*} head head node * @ * / function with a loop description to judge whether the list 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 met for the first time * @ * / function returns into the ring point 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)) } }Copy the code

Summary from: the journey of cartoon algorithm xiao Grey algorithm