leetcode 142. Circular linked list II

leetcode 142. Circular list Ⅱ

Hello everyone , I'm studying konjak in grade five of primary school , Focus on the back end , Witness the growth of konjaku together , Your comments, praise and attention are my biggest motivation , If you have any mistakes, please let me know , Thank you very much . Let's support originality ！ There is a mistake in writing .

Title Description

Given a linked list , 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 .

Answer key

Ideas ：

Use the speed pointer , The fast pointer moves two at a time, and the slow pointer moves one at a time , after n After the circle, we will meet , When meeting, because the fast pointer moves at a time, the two slow pointers move one at a time , So the fast pointer moves twice as many nodes as the slow pointer . The entry node of the ring linked list is the number of nodes left in the slow pointer unit circle , Another pointer can be used to start from the node , When the loop meets the slow pointer, it can get the entry node

/* * @lc app=leetcode.cn id=142 lang=cpp * * [142]  Circular list  II */

// @lc code=start
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution
{
    
public:
    ListNode *detectCycle(ListNode *head)
    {
    
        ListNode *slow, *fast, *p;
        slow = fast = p = head;
        while (fast && fast->next)
        {
    
            slow = slow->next;
            fast = fast->next->next;
            // Ring 
            if (slow == fast)
            {
    
                while (p != slow)
                {
    
                    p = p->next;
                    slow = slow->next;
                }
                return p;
            }
        }
        // Non ring 
        return nullptr;
    }
};
// @lc code=end