Leetcode 142. circular linked list II [knowledge points: speed pointer, hash table]

subject

source ： Power button （LeetCode）
link ：142. Circular list II
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source
Given the head node of a linked list head , Return to the first node of the link where the list begins to enter . If the list has no links , Then return to null.

If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）. If pos yes -1, There are no links in the list . Be careful ：pos Not passed as an argument , Just to identify the actual situation of the linked list .

No modification allowed Linked list .

Example 1：

Input ：head = [3,2,0,-4], pos = 1
Output ： The return index is 1 The linked list node of
explain ： There is a link in the list , Its tail is connected to the second node .

Example 2：

Input ：head = [1,2], pos = 0
Output ： The return index is 0 The linked list node of
explain ： There is a link in the list , Its tail is connected to the first node .

Example 3：

Input ：head = [1], pos = -1
Output ： return null
explain ： There are no links in the list .

Tips ：

The number of nodes in the list is in the range [0, 104] Inside
-105 <= Node.val <= 105
pos The value of is -1 Or a valid index in a linked list

Advanced ： Can you use O(1) Space to solve this problem ？

Problem solving

Method 1 ： Hash lookup （ Hashtable ）

Traversing the linked list , Map each node to a hash table , If a node already exists in the hash table , Then there is a ring and it is the ring inlet

• Write it yourself Hash surface ：（ The conflict resolution adopted is square detection ）

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */

#define MAXTABLESIZE 10000
typedef struct ListNode* ElementType;
typedef int Index;
typedef Index Position;
typedef enum{
     Legitimate, Empty, Deleted } EntryType;

typedef struct HashEntry{
    
    ElementType Data;
    EntryType Info;
}Cell;

typedef struct _HashTable{
    
    Cell* Cells;
    int TableSize;
}HashTable;

int NextPrime( int N )
{
    
    int i,P = (N%2)?N+2:N+1;

    while(1){
    
        for(i=(int)sqrt(P);i>2;i--){
    
            if(!(P%i)) break;
        }

        if(i == 2) break;
        else P +=2;
    }

    return P;
}

HashTable* CreateTable( int Size )
{
    
    HashTable* H = (HashTable*)malloc(sizeof(HashTable));
    H->TableSize = NextPrime( Size );

    H->Cells = (Cell*)malloc(H->TableSize*sizeof(Cell));

    for(int i=0;i<H->TableSize;i++){
    
        H->Cells[i].Info = Empty;
    }

    return H;
}

Position Hash( ElementType Key,int TableSize )
{
    
    return (int)Key % TableSize;
}

Position Find( HashTable* H,ElementType Key )
{
    
    Position CurrentPos,NewPos;
    CurrentPos = Hash( Key,H->TableSize );

    int Di;
    for(Di=0;Di<=H->TableSize/2;Di++){
    

        NewPos = (CurrentPos + Di*Di)%H->TableSize;
        if(H->Cells[NewPos].Info == Empty || H->Cells[NewPos].Data == Key) break;

        NewPos = (CurrentPos - Di*Di + H->TableSize)%H->TableSize;
        if(H->Cells[NewPos].Info == Empty || H->Cells[NewPos].Data == Key) break;
    }

    return NewPos;
}

bool Insert( HashTable* H,ElementType Key )
{
    
    Position Pos = Find( H,Key );

    if(H->Cells[Pos].Info != Legitimate){
    
        H->Cells[Pos].Info = Legitimate;
        H->Cells[Pos].Data = Key;

        return true;
    }else{
    
        return false;
    }
}

struct ListNode *detectCycle(struct ListNode *head)
{
    
    HashTable* H = CreateTable( MAXTABLESIZE );

    struct ListNode* p;
    for(p=head;p;p=p->next){
    
        
        if(!Insert( H,p )){
    
            break;
        }
    }

    free(H->Cells);
    free(H);

    return p;
}

• Call the third-party header file uthash.h( Header file only )

/* Structure definition */
struct _HashTable{
    
	struct ListNode* Key;
	UT_hash_handle hh;
};

/* Hashtable ： Initialize to empty table */
struct _HashTable* HashTable= NULL;

/* Implement your own lookup interface function ：*/
struct _HashTable* find( struct ListNode* iKey )
{
    
	struct _HashTable* temp;
	HASH_FIND_PTR( HashTable,&iKey,temp );
	return temp;
}

/* Implement its own plug-in interface function ：*/
void Insert( struct ListNode* iKey )
{
    
	struct _HashTable* temp = malloc(sizeof(struct _HashTable));
	temp->Key = iKey;
	HASH_ADD_PTR( HashTable,Key,temp );
}

struct ListNode* detectCycle(struct ListNode* head)
{
    
	struct ListNode* p = head;
	for(P=head;p;p=p->next){
    
		if(find(p)) break;
		Insert(p);
	}
	
	return p;
}

Method 2 ： Fast slow double pointer （ Optimal solution of this problem ）

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */

struct ListNode* detectCycle(struct ListNode* head)
{
    
    struct ListNode *fast,*slow;
    fast = slow = head;

    while(fast && fast->next){
    
        slow = slow->next;
        fast = fast->next->next;

        if(fast == slow){
    
            struct ListNode* Third = head;
            while( Third != slow){
    
                Third = Third->next;
                slow = slow->next;
            }

            return Third;
        }
    }
	
	return NULL;
}

Algorithm details ：142. Circular list II： Detailed explanation of fast and slow pointer Algorithm

• Ideas

The subject , Not only the operation of the linked list , And it also requires some mathematical operations .

Mainly investigate two knowledge points ：

• Determine whether the linked list is a ring
• If there are rings , How to find the entrance of this ring

Determine if the list has links
__________________________________________________________________________________
You can use the fast and slow pointer method , Defining the fast and slow The pointer , Start from the beginning ,fast The pointer moves two nodes at a time ,slow The pointer moves one node at a time , If fast and slow The hands meet on the way , It shows that the list has links .

Why? fast Take two nodes ,slow Take a node , If there is a ring , It's bound to meet in the ring , Instead of always staggering

First and foremost ：fast The pointer must enter the ring first , If fast Pointers and slow If the pointer meets , Must have met in the ring , There is no doubt that .

So let's see , Why? fast Pointers and slow The pointer must meet ？

You can draw a ring , And then let fast The pointer starts chasing at any node slow The pointer .

You will find that this is always the case in the end , Here's the picture ：

fast and slow Take another step , fast and slow Just met

This is because fast It's two steps ,slow It's a step , In fact, compared with slow Come on ,fast Is the proximity of a node to a node slow Of , therefore fast Must be able to communicate with slow coincidence .

The animation is as follows ：

If there are rings , How to find the entrance of this ring
__________________________________________________________________________________
Suppose from the head node to the ring entry node The number of nodes of is x. Ring entry node to fast The pointer and slow The pointer meets the node The number of nodes is y. From the meeting node And then to the ring entrance node, the number of nodes is z. As shown in the figure ：

So when we meet ： slow The number of nodes passed by the pointer is : x + y, fast Number of nodes passed by the pointer ： x + y + n (y + z),n by fast The pointer went inside the ring n Just met slow The pointer , （y+z） by Number of nodes in a circle A.

because fast The pointer is to walk two nodes in one step ,slow The pointer goes one node at a time , therefore fast Number of nodes passed by the pointer = slow Number of nodes passed by the pointer * 2：

(x + y) * 2 = x + y + n (y + z)

Eliminate one on both sides （x+y）: x + y = n (y + z)

Because you're looking for a circular entrance , So what is required is x, because x Express Head node to The distance of the ring entrance node .

So ask for x , take x Put it alone on the left ：x = n (y + z) - y ,

Again from n(y+z) To propose one （y+z） Come on , After sorting out the formula, it is the following formula ：x = (n - 1) (y + z) + z Note that there n Must be greater than or equal to 1 Of , because fast The pointer must go at least one more circle to meet slow The pointer .

What does this formula mean ？

• The distance from the meeting point to the entry point plus n-1 Ring length of circle , Exactly equal to the distance from the head of the linked list to the ring entry point .

That means ：

• 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 .

Why did you meet in the ring for the first time ,slow Of They count yes x+y instead of x + The length of several rings + y Well ？
__________________________________________________________________________________
First slow When entering the ring ,fast It must be the advanced ring .

If slow Ring inlet ,fast Also at the ring entrance , Then expand this ring into a straight line , Just like the following figure ：

You can see if slow and fast At the same time, start walking at the ring entrance , It must be at the ring entrance 3 meet ,slow Walk around ,fast Two rounds .

The key is coming. ,slow When entering the ring ,fast It must be anywhere in the ring , Pictured ：

that fast The pointer goes to the entrance of the ring 3 When , It's gone k + n Nodes ,slow Accordingly, we should go (k + n) / 2 Nodes .

because k Less than n Of （ And you can see that ）, therefore (k + n) / 2 Must be less than n.

in other words slow You must not have walked to the ring entrance 3, and fast It has reached the ring entrance 3 了 .

What does this mean ？

stay slow The link that began to walk has been connected with fast Met .

Then a classmate said again , Why? fast Can't skip ？ I have just said it once ,fast be relative to slow Is to move one node at a time , So it's impossible to jump over .

PS

Is this algorithm difficult ？ It's not hard to ！
Is mathematical analysis difficult ？ It's not hard to ！
Can you think of it ？ Can't think of ！