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

Circular linked lists

The title

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

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 that pos is only used to identify the case of the ring and is not passed to the function as an argument.

Example 1:

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

Example 2:

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

Example 3:

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

Answer key

From the introduction of the previous article we know how to prove the existence of rings in linked lists. This time we on the basis of the previous implementation of the list to return the first node into the ring.

solution

  • Because [through the introduction of the previous article] in solution one through the linked list way to pass every nodesetWay toMapIn the object.
  • setBefore you go throughhasWay to determineMapObject, which returns the node directly.

Code implementation

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

Spatial complexity

Because the space occupied by the Map object in the above code is affected by the linked list, the space complexity is O(N).

Spatial complexity

The time complexity of traversing the list through while in the above code is O(N) affected by the length of the list.

The advanced

Can you solve this problem with O(1) (i.e., constant) memory?

Ask questions

From the introduction of the previous article, we can only determine whether there is a ring in the linked list, so how do we determine the first node into the ring?

Analysis of the

  1. fast,slowAnd starting at the beginning node,fastTake two stepsslowWalk the one step

2. The first execution result is as follows

  1. The second execution result is as follows

4. The result of the third execution is as follows

  1. The fourth result is as follows

  1. The fifth result is as follows

  1. It can be seen from the above five execution results that at the green nodefast,slowMeet again

  • Let’s call the first node from the head node to the entry node A
  • Put the first node into the ring tofast,slowThe nodes that meet are called B
  • fast,slowThe first node from the meeting node to the entry node is called C
  • That is, as shown in the diagram above

Fast: A +n(b+ C)+b slow: a+b where N stands for the number of laps taken by fast, that is, n >= 1

Combining all of the above we can come up with a formula

2 (a + b) = a + n + b (b + c) where n > = 1 conversion: a = b + (n – 1) nc conversion: a = (n – 1) + c (b + c)

  • According to the figure above, n is 1 turn
  • Wait for againa=c

Now, one might say, well, n is definitely going to change with the number of times you go before you go in the loop. So n doesn’t have to be 1 to meet. In fact, it doesn’t matter how many times you go before you go in or how many times you go in, it’s always going to happen, so you can go down and try it out for yourself.

From a=c, as long as we have a pointer temp starting at head every step we take and slow continues, they will eventually meet at the first entry point.

Code implementation

/** * @param {ListNode} head * @return {ListNode} */ var detectCycle = function(head) { if(head == null || head.next == null) return null; let fast = head; let slow = head; while(fast ! == null && fast.next ! == null){ fast = fast.next.next; slow = slow.next; if(fast == slow){ let temp = head; while(temp ! == fast){ fast = fast.next; temp = temp.next; } return fast; } } return null; };Copy the code