©2020-2024 ioDraw All rights reserved
Title Requirements
Given a linked list , Judge whether there are links in the linked list . If there is a node in the list , It can be tracked continuously next The pointer reaches again , Then there are rings in the linked list . If there are rings in the linked list , Then return the node into the ring
. otherwise , return NULL.
thinking
Set speed pointer , The fast pointer takes two steps at a time , The slow pointer takes one step at a time , If there's a ring , After the fast and slow pointers enter the loop at the same time , The fast pointer will catch up with the slow pointer , Their addresses will be equal , then , From the meeting place of the fast and slow pointers and the head node of the linked list , Start two pointers separately , Take a step , The two pointers will meet at the entry loop , Return to the node .
graphic
code implementation
struct ListNode *detectCycle(struct ListNode *head) { struct ListNode * fast =
head; struct ListNode * slow = head; while (fast && fast->next) { fast =
fast->next->next; slow = slow->next; if (fast == slow) { struct ListNode*
slowHead = head; while (slow != slowHead) { slow = slow->next; slowHead =
slowHead->next; } return slow; } } return NULL; }
Technology