“This is the 24th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

describe

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
Copy the code

Example 2:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
Copy the code

Note:

The number of the nodes in the list is in the range [0, 10^4].
-10^5 <= Node.val <= 10^5
pos is -1 or a valid index in the linked-list.
Copy the code

parsing

Given the head node of the linked list, return the node at the beginning of the loop. If there is no loop, null is returned.

If there is a node in the list that can be reached again by following the next pointer over and over again, then there is a loop in the list. Internally, POS is used to represent the index (0-indexed) of the node to which next points to the node that starts the end of the linked list, which is essentially a loop point. If there is no loop, it is -1. Note that pos is not passed as an argument, and the list cannot be modified. Can you use O(1) memory to solve the problem?

This problem is actually in examining how positioning list entry, central location, we first use the most common method to solve this problem, with our most simple idea, is certainly a traversal of the list, will traverse to a node in a set s, arrive if a node has appeared in the set s, it means that the node is the entry of the ring, In example 1 above, when traversing the list reaches the second node for the second time, there is already one in the set, so this node is the entrance to the ring. The time complexity of this solution is O(n), but the space complexity is O(n). Although it can pass, it does not meet the high requirements of the problem using O(1) in memory.

In fact, this also illustrates a most simple truth, the more simple and violent algorithm may consume more resources, the more sophisticated algorithm will consume less resources, of course, this is not absolute, only relative.

answer

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        s = set()
        while head:
            if head not in s :
                s.add(head)
            else:
                return head
            head = head.next
        return None
        	      
		
Copy the code

The results

Linked List Cycle II in the Linked List given in the Linked List. 20.1 MB, less than 16.53% of Python online submissions for Linked List Cycle II.Copy the code

parsing

In fact, more space is consumed in order to find the second point. In fact, we can completely save this part of space consumption and judge whether there is a ring by traversing the fast and slow Pointers. But this is only the first step.

Suppose that the fast pointer and the slow pointer meet, the fast pointer and the slow pointer both go through the entrance of m nodes to enter the ring, the fast pointer goes through a circle and takes b more steps, and the slow pointer goes through c circle and takes B more steps, because the distance of the fast pointer is twice that of the slow pointer, and the length of the ring is N, so the relationship is

 m + a*n + b = 2(m + c*n + b) 
Copy the code

After simplification, it is:

(a-2c)*n = m+b
Copy the code

Because the slow pointer has taken b more steps than the integer circle, combining with the above formula, we can find that if the slow pointer takes another M steps, it will come back to the integer circle, which is the entrance to the ring. At this time, m means that the head of the linked list and the slow pointer continue to move backward at the same time, and the place where they meet is the entrance.

Also pay attention to the boundary conditions. If head is empty, you can return it directly. It is ironic that every time you remind someone of the boundary conditions, you get stuck by the boundary conditions.

answer

class Solution(object): def detectCycle(self, head): """ :type head: ListNode :rtype: ListNode """ if not head: return slow = head fast = head tmp = None while fast.next and fast.next.next: slow = slow.next fast = fast.next.next if slow == fast: tmp = slow break if not tmp: return while head ! = slow: head = head.next slow = slow.next return slowCopy the code

The results

Linked List Cycle II in the Linked List given in the Linked List. Linked List Cycle II for the Linked List submissions in the Linked List.Copy the code

Original link: leetcode.com/problems/li…

Your support is my biggest motivation