To the chase

Circular linked list II

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

Resolution:

It has been mentioned in the previous article to judge whether a linked list is a ring list. Please refer to the article to judge whether a linked list is a ring

Two methods are mainly used in the above article, one is the array cache method, the other is the two-pointer tortoise and rabbit race algorithm without opening up new array space, but the tortoise and rabbit race method is only suitable for judging whether the ring is formed, and can not directly get the node in which the ring is formed. The reason is that “turtle” and “rabbit” may not meet at the last node, and it is unknown which node they meet at. So if you want to find the nodes of a ring, this is not a good way to do it.

So how do we find the nodes of the ring? Consider the first method, array caching.

When the list traverses, the list is recorded in the array. When the element in the array appears again, it means that the list is looped, and the looped node is the last element of the array.

Similarly, we can use faster lookups and replace arrays with maps.

Create a Map and iterate through the list, if the Map does not exist then map.set, if there is then return map.get, logical clear, simple method!!

There should be no need to explain too much, the code:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
   let map = new Map()
   map.set(head, head)
   while(head) {
       head = head.next
       if (map.has(head)) {
           return map.get(head)
       } else {
            map.set(head, head)
       }
       
   }
   return null
};
Copy the code