Double pointer

Double Pointers can generally be divided into two categories, one is fast and slow Pointers, one is left and right Pointers. Fast and slow Pointers are usually used to solve problems in linked lists, such as determining whether a linked list contains rings, and left and right Pointers are mainly used to solve array/string problems, such as binary search, which is mainly solved by fast and slow Pointers

How fast a pointer

  1. Initialization: Both Pointers point to the list head node head
  2. Forward: fast pointer fast in front, slow pointer after

Check whether the list has rings

  1. Each node of a linked list knows only the next node, so a pointer cannot determine whether there is a ring or not. If there is no ring in the list, the pointer will eventually encounter null, and the list will be terminated
  2. But if there are rings in the list, you’re stuck in an infinite loop because there are no null tail nodes in the list.
  3. Therefore, to determine whether a single linked list contains rings, the classical solution is to use double Pointers, one running fast and one running slow. If there is no ring, then the fast pointer will encounter NULL, but if there is a ring, then the fast pointer will exceed the slow pointer one circle, and finally meet the slow pointer.
boolean isHasCycle(ListNode head){
    ListNode fast,slow;
    // The fast and slow Pointers point to the head
    fast=slow=head;
    // If the end of the list is not reached
    while(fast! = =null&&fast/next! = =null) {// The fast pointer takes two steps at a time
        fast = fast.next.next;
        // Slow the pointer one step at a time
        slow = slow.next;
        // If fast and slow Pointers meet, a loop exists, and true is returned
    }
    // If the end of the list is null, the list does not contain rings, return false
    return false
}
Copy the code

Return the starting position of a linked list containing rings

This problem is not difficult, let’s talk about the method first. The method is: when the fast and slow Pointers meet, set either of them to point to the head of the list, and then let the two Pointers move at the same speed, so that when they meet again, the node is at the beginning of the ring.

  1. At the first encounter, assuming that the slow pointer took K steps, then the fast pointer must have taken 2k steps, which means that slow took k extra steps, which is the length of the ring
  2. Assuming that the distance between the encounter point and the beginning of the ring is m (shown in orange), then the distance between the beginning of the ring and the head node head is k-m. This is because the slow pointer takes K steps, including the distance between the head node and the beginning of the ring (the green line) and the beginning of the ring to the encounter point (the orange part). If the distance between the beginning of the ring and the head node is M, the distance between the beginning of the ring and the head node is k-M. But because the length of the entire ring is K, a further k-m step from the encounter point (the green curve) will also reach the beginning of the ring, exactly the same distance as the head node and the beginning of the ring.
  3. So we just need to re-point either of the fast or slow Pointers to head, and then the two Pointers move at the same speed. After k-M steps, the two Pointers must meet, and the meeting point is the starting point of the ring
  4. The code is:
ListNode detectCycle(ListNode head){
       ListNode fast,slow;
       fast = slow = head;
       while(fast! =null&&fast.next! =null){
           fast = fast.next.next;
           slow= slow.next;
           if(fast==slow) break;
       }
       // Let one of the Pointers point to the header pointer
       slow = head;
       while(slow! =fast){ slow = slow.next; fast = fast.next; }// Where the two Pointers meet is the starting point
       return slow;
   }
Copy the code