[B] [C] [D]

Given a linked list, if it is looped, implement an algorithm that returns the beginning node of the loop. If the ring does not exist, return NULL.

If there is a node in the list that can be reached again by following the next pointer continuously, then there is a ring in the list. To represent the rings in a given list, we use the integer pos to represent where in the list the tail joins (the index starts at 0). If pos is -1, there are no rings in the linked list. Note: POS is not passed as an argument, just to identify the actual state of the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1 output: tail connects to node index 1Copy the code

Example 2:

Input: head = [1,2], pos = 0 output: tail connects to node index 0 description: a linked list has a loop whose tail connects to the first node.Copy the code

Example 3:

Input: head = [1], pos = -1 Output: no cycleCopy the code

Advanced:

  • Can you solve this problem without extra space?

If the list has a loop, return the first node of the loop, otherwise return null

The solution is as follows:

If the current node has a tag, it means that the node has been traversed before. If the node is traversed again, it means that the node is the beginning node of the linked list loop. Return it

Otherwise, assign a value to the tag attribute of the node (there is no requirement to assign a value, as long as you can determine whether there is a tag), and continue traversing the list backwards

If no previously traversed node is encountered until the end of the list, the list has no loops and null is returned

The demonstration process is as follows:

The code is as follows:

Var detectCycle = function(head) {while(head){if(head. Tag) return head; // Instead, tag the node with tag head.tag = 'been'; head = head.next; } // If the list does not encounter the node that was traversed before, there is no loop in the list. };Copy the code

This completes leetcode- Interview question 02.08- Loop detection

If you have any questions or suggestions, please leave a comment!