Continuously update the force buckle , Two solutions to each problem

A quick solution , A kind of brain shell solution

Catalog

Title Description

  Answer key 1： Use set

Answer key 2： Fast and slow pointer to find the law

---

Title Description

Topic link ：

https://leetcode-cn.com/problems/linked-list-cycle-ii/

subject ：

  Example ： requirement ： Return to node 2

  Answer key 1： Use set

Thought is to use ArrayList<> aggregate , Store the linked list nodes into the set one by one

If the list has links , As shown in the example ,head End of traversal -4 after , To traverse 2, Judged 2 Already stored in the collection , There are links in the list

Icon ：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //  If there are no nodes , Or just one node , There can be no ring 
        if (head == null || head.next == null)  return null;

        ListNode cur = head;

        //  Use extra space 
        ArrayList<ListNode> list = new ArrayList<ListNode>();

        while (cur.next != null) {
            // Store the node at this time in the collection 
            list.add(cur); 

            //  Pointer backward 
            cur = cur.next;

            //  If there are already stored in the collection cur, Then return it 
            if (list.contains(cur)) {
                return cur;
            }

        }
        //  Loop exit means cur It's empty , There are no links in the linked list 
        return null;
    }
}

Answer key 2： Fast and slow pointer to find the law

Seeing the speed pointer, did you think of “ Circular list 1” This question ？ But these two questions are different , The position where the fast and slow pointers meet is uncertain , As the number of nodes changes , The place of meeting is also different

  So how to find the starting point of the ring ？ This requires a little mathematical knowledge

As shown in the figure , Starting from P, The intersection of the linked list and the ring is Q, The fast pointer and the slow pointer first met in R

  hypothesis

PQ Long for x    QR Long for y

The circumference of the ring is c

Slow the pointer to R Let's go at two o'clock ：

L slow = x + λc + y;   （λ Indicates the number of turns of slow pointer movement , As a positive integer ）

L block = x + βc + y;①（β Indicates the number of turns of the fast pointer , As a positive integer ）

Because the pointer takes two steps , Slow pointer takes one step , therefore   L fast = 2 * L slow

namely ：L fast = 2 * （x + λc + y）;②

① And ② All represent the distance the fast pointer moves , The two formulas are equal

x + βc + y =  2 * （x + λc + y）

Simplify ：x + y = （β - 2*λ）c

  because β and λ Are integers. , therefore （ β - 2*λ ）* c Is the integer circle of a ring , At this point, the answer has come out , If you don't understand , We continue ：

hypothesis （ β - 2*λ ） yes 3,

and   x + y The journey is Cyclic 3  circle namely ：x + y = 3c

At this point, the fast pointer and the slow pointer meet , Let's stop them

Define another pointer p, Let it move from the beginning , One node at a time , When he moves to Q a.m. ,p The journey is x

Then the pointer goes slowly （ Two laps + c - y）,c - y How much is? ？

  If you don't understand , We can bring it in ,

Here is the code ：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        //  If there is no node or only one node , There must be no ring , Go straight back to 
        if (head == null || head.next == null) return null;

        //  Speed pointer 
        ListNode fast = head;
        ListNode slow = head;

        while (true) {
            //  Prevent null pointer exception , stay “ Circular list 1” Said in 
            if (fast.next == null || fast.next.next == null) 
                  return null;

            //  Go two steps at a time 
            fast = fast.next.next;

            //  Slow pointer one step at a time 
            slow = slow.next;

            //  Fast and slow hands meet , stop 
            if (fast == slow) {
                break;
            }
        }

        //  Define a pointer p Run with the slow pointer , Both hands reach the starting point of the ring at the same time 
        ListNode p = head;

        while (p != slow) {
            p = p.next;
            slow = slow.next;
        }
        return p;
     
    }
}