I am participating in the creation activity of the Nuggets newcomer to start the road of writing together

Come on second practice

142. Circular linked List II

Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless.

This problem can be solved in a similar way to circular list I.

Method 1: Traverse the storage

Traversing through the ‘head’, each traversed node is stored in a container, if the subsequent traversal to the stored node, it indicates that there is a ring, and this first identical node is the first node into the ring

var detectCycle = function(head) { if (! head || ! head.next) return null; var mapper = new Map(); while(head){ if(mapper.has(head)){ return head } mapper.set(head, head); head = head.next } return null };Copy the code

Method two: fast and slow pointer

When the fast and slow Pointers can meet, it means there is a ring. When the two Pointers meet, let the other pointer start from the beginning node at the speed of the slow pointer, then the node where this pointer and the slow pointer meet is the entry point. It needs to be derived:

  • The distance from the head node to the entry point is L0;
  • Distance L1 from entry point to first encounter point;
  • The distance from the first encounter point to the entry point is L3;
  • The distance covered by the slow pointer when meeting: S = L0 + L1;
  • The distance traveled by the fast pointer when meeting: F = 2S = S + n(L1 + L2);
  • So L0 is equal to n minus 1 times L1 plus L2 plus L2
  • The distance from the head node to the entry point = the distance from the first entry point to the entry point of the loop (n-1) circle, and then back to the entry point

  • If slow takes K steps when the fast and slow Pointers meet, then FAST takes 2k steps;
  • It can be seen from the figure above that fast takes k more steps than slow and turns n times inside the ring.
  • Assuming that the distance from the starting point of the ring to the encounter point is M, then the distance from the head node to the starting point of the ring is k-m, that is, k-M steps from the head node can reach the starting point of the ring.
  • If you continue from the meeting point, k-M steps will also arrive at the beginning of the ring. (If you take k steps from the meeting point to return to the meeting point, then k-M steps will definitely arrive at the beginning of the ring.)
  • We re-point either of the fast or slow Pointers to head, and then the two Pointers move at the same speed. K-m steps later, the two Pointers must meet, and the place where they meet is the starting point of the ring
var detectCycle = function(head) { if (! head || ! head.next) return null; var fast = head,slow = head while(fast){ if(! fast.next){ return null } slow = slow.next fast = fast.next.next if(fast == slow){ fast = head; while (fast ! = slow) { fast = fast.next; slow = slow.next; } // return fast; } } return null };Copy the code