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.

Data structure:

class ListNode {
      val: number
      next: ListNode | null
      constructor(val? : number, next? : ListNode |null) {
          this.val = (val===undefined ? 0 : val)
          this.next = (next===undefined ? null : next)
      }
  }
Copy the code

Ideas:

Judge to have a ring:

Same as ring linked list

Judgment starting point:

Suppose that the fast and slow Pointers meet at the dot in the figure, then: Since the speed of the fast pointer is twice that of the slow pointer, the distance covered by the fast pointer is twice that of the slow pointer. The distance traveled by the slow pointer is a+b, and twice that is 2(a+b). At this point, the fast Pointers have gone through A, gone through n cycles in the ring, and finally meet at the midpoint of the graph. So the fast pointer goes through a plus n times b plus c plus b. Write the equation as 2(a+b) = a+ n(b+c) +b. A =(n-1)b + nc

Through the final equation, we can find that the distance from the head point to the entry point is A, and the distance from the meeting point in the figure to the entry point is exactly (n-1) B + NC. Therefore, we start from head and the point at the same time, and the meeting point is the entry point.

code

function hasCycle(head: ListNode | null) :boolean {
    let fast = head,slow = head;
    while(fast && fast.next){
        fast = fast.next.next;
        slow = slow.next;
        if(fast === slow){
            let ptr = head;
            while(ptr! =slow){ ptr = ptr.next; slow = slow.next; }returnptr; }}return null;
}
Copy the code