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.

** Does not allow modification of a given linked list.

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify 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?

Follow-up: Can you solve it without using extra space?

Answer:

It’s just one more step than the last problem to figure out where the entry point is. Two methods:

Hash table:

When a node is added to a hash table, it is found that the node already exists. And the existing node is the entry point

Double pointer:

I drew a picture to help understand:

The speed of the fast node is 2 and the speed of the slow node is 1:

When they met:

The slow node goes: A + B

Since the fast pointer is twice as fast as the slow pointer, the fast node is gone: 2(a+b)

When fast and slow nodes meet, the fast node just goes one more circle than the slow node. The fast node goes :(a+b)+(b+c).

2(a+b)=(a+b)+(b+c)

A = c solution

In other words, the length from the encounter node to the entry point is the same as the length from the head node to the entry point

It can be concluded that if one of the slow or fast nodes points to the head node and the other stays at the encounter node, then the speed is 1 and the linked list continues to be traversed, the node when the two Pointers meet again happens to be the entry point.

Note: In order to facilitate understanding, length B is defined as the length of the upper part. In fact, b should be the total length of the slow node to bypass the circular linked list when the fast and slow nodes meet

Hash table solution:

Java:

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) returnnull; // Set<ListNode> nodeSet = new HashSet<>(); // create a hash tablewhile(head.next ! = null) {// The next list is not nullif (nodeSet.contains(head)) returnhead; Nodeset.add (head); nodeset.add (head); // Add node head = head. Next; // move down one bit}returnnull; }}Copy the code

Python:

class Solution(object):
    def detectCycle(self, head):
        """ :type head: ListNode :rtype: ListNode """
        if head is None:
            return None
        hashSet=set(a)# construct set
        while(head.next is not None):
            if head in hashSet:# Whether it already exists
                return head
            hashSet.add(head)
            head=head.next
        return None
Copy the code

Double pointer solution:

Java:

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast ! = null && fast.next ! = null) {// Whether the fast pointer and its next bit are null slow = slow.next; fast = fast.next.next;if(slow == fast) {// If the same, there is a circular list slow = head; // point to the head nodewhile(slow ! = fast) {// continue traversing, the next node is the entry point slow = slow.next; fast = fast.next; }returnslow; }}returnnull; }}Copy the code

Python:

class Solution(object):
    def detectCycle(self, head):
        """ :type head: ListNode :rtype: ListNode """
        if head is None or head.next is None:
            return None
        slow, fast = head, head
        while fast is not None and fast.next is not None:
            slow, fast = slow.next, fast.next.next
            if slow == fast:
                slow = head
                whileslow ! = fast: slow = slow.next fast = fast.nextreturn slow
        return None
Copy the code

Welcome to the public account: love to write Bug (ID: iCodeBugs)