Foreword

This series mainly organizes the hand-tear code questions that need to be mastered in the interview.This section describes the problem of having cycles in linked lists.

First, BM6 determines whether there is a cycle in the linked list

(1) Set the fast and slow pointer, and the fast pointer moves at a timeTwo spaces, the slow pointer moves one space at a time;
(2) If the fast pointer is not empty, then it will keep looping;
(3) If the fast pointer is equal to the slow pointer, it proves that there is a cycle in the linked list, if the fast pointer is equal to the slow pointerIf the pointer is empty, it proves that there is no cycle in the linked list.

function hasCycle( head ) {// write code herevar slow = head;var fast = head;while(fast && fast.next){slow = slow.next;fast = fast.next.next;if(slow == fast) return true}return false}

Second, the entry node of the ring in the BM7 linked list

(1) Set the fast and slow pointer, the fast pointer moves two spaces at a time, and the slow pointer moves one space at a time;
(2) Same as the previous question, if the fast pointer == the slow pointer, it proves that there is a loop, and if the fast pointer is empty, there is no loop;
(3) If the fast pointer is equal to the slow pointer, let the slow pointer start from the beginning,Both hands move forward one frame at a time, and when the fast hand equals the slow hand, that position is the beginning of the ring.