“This is the 21st day of my participation in the Gwen Challenge in November. See details: The Last Gwen Challenge in 2021”

[B] [C] [D]

Given a linked list, return the first node where the list begins to loop. Returns NULL if the list is loopless.

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, the metric system internally uses the integer POS to represent where the tail of the list is connected to in the list (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.

Linked lists are not allowed to be modified.

Example 1:

Input: head = [3,2,0,-4], pos = 1 output: returns the list node with index 1.Copy the code

Example 2:

Input: head = [1,2], pos = 0 output: returns a list node with index 0.Copy the code

Example 3:

Input: head = [1], pos = -1 Output: returns NULL Explanation: There are no loops in the linked list.Copy the code

Tip:

  • The number of nodes in a linked list ranges from[0, 104] 内
  • -105 <= Node.val <= 105
  • posThe value of- 1Or a valid index in a linked list

Advanced: Can you solve this problem using O(1) space?

This question is very simple answer ha, the solution idea is as follows:

  1. The first step is to identify the case where the list is empty. If the list is empty, returnnull
  2. Traverses the list. If the current node is not marked, it is marked that the node has been traversed
  3. If the list has no loops, the entire traversal goes to the end of the list and returnsnullCan be
  4. If the list has a loop, it will traverse to a node that has already been marked. This node is the first node entered into the loop, and it can be returned to the node

The overall process is as follows:

The code is as follows:

Var detectCycle = function(head) {if(head === null) return null; If (head. Tag) return head; if(head. Tag) return head; if(head. // Otherwise add the tag head.tag = 'been' head = head.next; } // If traversal reaches the end of the list, return null return null; };Copy the code

This completes leetcode-142- Circular linked List II

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