LeetCode160 ＆ LeetCode141——double pointers to solve the linked list

Summarize two algorithm problems about linked lists at one time , These two problems are solved with Speed pointer The basic idea of . in fact , The problem of loop in the linked list is often inseparable from the fast and slow pointer solution , So we should establish this reflection of thinking .
The first is the intersecting linked list , seeing the name of a thing one thinks of its function , This problem is to judge whether the two linked lists are unified after a certain node , The questions are as follows ：

In fact, if you analyze it carefully , It can be found that the difficulty of this problem is that if there is really an intersection in the two linked lists , They are There is no length of the part before the intersection Is not uniform , And we're not sure how much difference there is between the two , The pointer running at the same speed will inevitably miss this intersection . So the starting point of the final solution of this problem is Artificially flatten the distance between them , So that when two pointers with the same speed starting from the heads of the two linked lists meet ( If you can ) The journey is the same , In this case, it can be concluded that ： If two linked lists do intersect , There must be some intersection , At this intersection, the two pointers passing through the distance balance will definitely meet , This is the solution to the whole problem .

So how to level the distance artificially ？ The way is ： Let from the linked list A The pointer whose head starts to move is walking through the linked list A Then start from the linked list B Your head starts moving again , On the contrary, the same . In this way, the length gap between the two linked lists is filled . If two linked lists don't intersect , It can be concluded that if there is no intersection when any pointer reaches the end of its list for the second time , Then you can jump out of the loop and assert that the search failed , Because if there were really intersections, they would have intersected before .

Here is the code I wrote , For coding convenience , I wrote one shiftTrack Function to help pointer convert linked list tracks ,bool The return value indicates whether the conversion is successful , In fact, you are judging whether the search fails . For each pointer , There is one pair To record its information ,first The element records the head of the linked list from which it starts ,0 Express A Linked list ,1 Express B Linked list ;second The element indicates whether it has been converted before , This is an important basis for judging whether the search fails .

bool shiftTrack(ListNode*& Ptr, pair<bool, bool>& Flag, ListNode *headA, ListNode *headB)
{
    
    /*if the present pointer has not been on another track*/
    if(Flag.second == 0)
    {
    
        /*Ptr1*/
        if(Flag.first == 0)
            Ptr = headB;
        /*Ptr2*/
        else
            Ptr = headA;
        
        Flag.second = 1;
        return true;
    }
        
    return false;
}    

Then the main program code , It uses while true…break Design example .

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    
        /*declare 2 pointers*/
        ListNode* Ptr1 = headA;
        ListNode* Ptr2 = headB;

        /*success flag*/
        bool Success = false;

        /*the first element indicating which one the pointer is*/
        /*the second element indicating whether the pointer has been on another track*/
        pair<bool, bool> Flag1 = make_pair(0, 0);
        pair<bool, bool> Flag2 = make_pair(1, 0);

        while(true)
        {
    
            /*if the intersection point is founded, jump out of loop*/
            if(Ptr1 == Ptr2)
            {
    
                Success = true;
                break;
            }
            else
            {
    
                /*modify the pointer to next position*/
                if(Ptr1->next != nullptr)
                    Ptr1 = Ptr1->next;
                else if(!shiftTrack(Ptr1, Flag1, headA, headB))
                    break;

                if(Ptr2->next != nullptr)
                    Ptr2 = Ptr2->next;
                else if(!shiftTrack(Ptr2, Flag2, headA, headB))
                    break;
            }
        }

        if(Success)
            return Ptr1;
        else    
            return nullptr;
    }

This is an overview of using fast and slow pointer algorithm to solve the intersection problem of two linked lists . similarly , There is also the following question , This problem does not involve two linked lists , It is Judge whether there is a loop inside a linked list ：

This problem also uses two pointers , The difference is that these two pointers are artificially Exercise at different rates . The principle is simple , It's like running on the school playground , One runs fast and the other runs slowly , Such a fast runner will repeatedly catch up with a slow runner , This proves from the side that the runway is circular , Otherwise, it is impossible to catch up .

So the key point of this question is , Let the two pointers run at different speeds , If there is a self ring , The fast pointer will catch up with the slow pointer , When you meet, you can assert that there is a loop in the linked list , If you reach the end of the list, there is no self ring , That is, there is no self ring . The first is to realize Take a step forward Function of oneStepForward：

bool oneStepForward(ListNode*& Ptr)
{
    
    /*if the next position is null, return false*/
    if(Ptr == nullptr || Ptr->next == nullptr)
        return false;

    /*switch to the next position*/
    Ptr = Ptr->next;
    return true;
}

And then there was Take two steps forward Function of twoStepForward, through oneStepForward To achieve ：

bool twoStepForward(ListNode*& Ptr)
{
    
    /*implement the function through oneStepForward*/
    if(!oneStepForward(Ptr) || !oneStepForward(Ptr))
        return false;
    return true;
}

Then is the logical implementation of the main algorithm ：

bool hasCycle(ListNode *head) {
    
    /*if the list is null...*/
    if(head == nullptr)
        return false;

    /*declare 2 pointers here, let 1 pointer chase another 1 */
    ListNode* Fast = head->next;
    ListNode* Slow = head;

    while(true)
    {
    
        if(Fast != Slow)
            if(!oneStepForward(Slow) || !twoStepForward(Fast))
                return false;
            else continue;
        else
            return true;
    }
}