LeetCode142. Circular linked list II [two pointers, two methods for judging links in the linked list and finding ring points]

LeetCode142. Circular list II

1. subject

2. Ideas

Two steps ：
1. Determine whether there is a ring —— Fast and slow pointer method
It should be noted that : We will meet , Because after entering the ring, it is equivalent to fast The pointer moves forward one chase at a time slow The pointer

2. Look for the entrance of the ring
a. Start a pointer from the beginning node , From the meeting node Also start a pointer , These two pointers walk only one node at a time , So when these two pointers meet, it is The node of the ring entrance .
Here is the mathematical proof ：

n If it is greater than 1 The situation of , Namely fast The pointer turns in a circle n After the circle, I met slow The pointer . Actually sum n by 1 When The effect is the same , You can also find the circular entry node through this method , It's just ,index1 The pointer is in the ring Turn more (n-1) circle , Then meet again index2, The meeting point is still the entrance node of the ring .

b. Disconnect list , Combine the problem of linked list intersection to find the beginning

3. Code implementation

（1） Determine whether there is a ring

//1. Set the speed pointer to the header 
		ListNode* fast = head;
		ListNode* slow = head;
//2.fast Take two steps at a time  slow One step at a time 
		// It's not good to write like this ！ If fast->next It's empty , Cannot access fast->next->next！
		//while(fast->next != NULL && fast->next->next != NULL)
		while(fast!=NULL && fast->next !=NULL)
		 {
    
		 	fast = fast->next->next;
			slow = slow->next;
			if(fast == slow) break;// Equal to jump out 
		 }
//3. The condition used to determine the jump is fast == slow still fast Empty finger 
		 if(fast==NULL || fast->next == NULL)
		 	return NULL;

matters needing attention

1. It's not good to write like this ！ If fast->next It's empty , Cannot access fast->next->next！
while(fast->next != NULL && fast->next->next != NULL)
2. The cyclic condition cannot be while(fast != slow), In this case, the acyclic condition cannot be distinguished ！

（2） Look for the entrance of the ring

a. Mathematical methods Set two more pointers

		 ListNode* p1 = fast;// Start a pointer from the encounter node 
		 ListNode* p2 = head;// Start a pointer from the beginning node 
		 while(p1 != p2)
		 {
    
		 	p1 = p1->next;
		 	p2 = p2->next;
		 }
		 return p1;// The encounter node is the linked list entry 

b. Disconnect list , Join linked list intersection

		//ListNode *x;x->next = fast;x->next = NULL  That's not right ！
		ListNode* p = fast;
		while(p->next != fast)
		p = p->next;
		p->next = NULL;
		
		// Become two linked lists , One by head start   A meeting point fast start 
		ListNode* m = head; ListNode* n = fast;
		// Count the length of the two linked lists 
        int len1 = 0;int len2 = 0;
		while(m!= NULL) {
    m = m->next;len1 ++;}
		while(n != NULL){
    n = n->next;len2++;}
		
		if(len1 > len2){
    
			int n = len1 - len2;// Calculate the linked list difference 
			while(n--){
    // The pointer of the long linked list goes backward first , Align with the pointer of the short linked list 
				head = head->next;
			}
			while( head != fast)// Step back synchronously , Until equal nodes are encountered .
			{
    
				head = head->next;
				fast = fast->next;
			}
			return head;
		}
		else{
    
			int n = len2 - len1;
			while(n--){
    fast = fast->next;
			}
			while( head != fast)
			{
    
				head = head->next;
				fast = fast->next;
			}
			return head;
		}

matters needing attention

ListNode *x;x->next = fast;x->next = NULL, Never write that ！ The single linked list cannot access the node in front of it ！

Complete code

Method 1 ：

class Solution {
    
public:
    ListNode *detectCycle(ListNode *head) {
    
        ListNode* fast = head;
		ListNode* slow = head;
        while(fast!=NULL && fast->next !=NULL)
		 {
    
		 	fast = fast->next->next;// Two steps at a time  
			slow = slow->next;		// One step at a time 
			if(fast == slow) break;
		 }
		 if(fast==NULL || fast->next == NULL)
		 	return NULL;
		 	ListNode* p1 = fast;// Start a pointer from the encounter node 
		 ListNode* p2 = head;// Start a pointer from the beginning node 
		 while(p1 != p2)
		 {
    
		 	p1 = p1->next;
		 	p2 = p2->next;
		 }
		 return p1;// The encounter node is the linked list entry 
}
};

Method 2 ：

class Solution {
    
public:
    ListNode *detectCycle(ListNode *head) {
    
        ListNode* fast = head;
		ListNode* slow = head;
        while(fast!=NULL && fast->next !=NULL)
		 {
    
		 	fast = fast->next->next;// Two steps at a time  
			slow = slow->next;		// One step at a time 
			if(fast == slow) break;
		 }
		 if(fast==NULL || fast->next == NULL)
		 	return NULL;
		
		ListNode* p = fast;//ListNode *x;x->next = fast? 
		while(p->next != fast)
		p = p->next;
		p->next = NULL;
		
		// Become two linked lists , One by head start   A meeting point fast start 
		ListNode* m = head; ListNode* n = fast;
		while(m!= NULL) {
    m = m->next;len1 ++;}
		while(n != NULL){
    n = n->next;len2++;}
		
		if(len1 > len2){
    
			int n = len1 - len2;
			while(n--){
    
				head = head->next;
			}
			while( head != fast)
			{
    
				head = head->next;
				fast = fast->next;
			}
			return head;
		}
		else{
    
			int n = len2 - len1;
			while(n--){
    fast = fast->next;
			}
			while( head != fast)
			{
    
				head = head->next;
				fast = fast->next;
			}
			return head;
		} 
		
    }
};