The interviewer asked me how to find the entrance in the linked list. I thought it was simple but I wanted to be silly on the spot

The question of whether there is a link in the linked list seems simple, but there are a lot of things to pay attention to in actual handling. This question is a very high-frequency written test interview question. If the memory is not strong, it is easy to forget. You can take a serious look at the study! A small partner met in a certain hand interview.

Determine whether the linked list has a ring

Title description:
Given a linked list, determine whether there are loops in the linked list.

If there is a node in the linked list that can be reached again by continuously tracking the next pointer, there is a ring in the linked list.

If there is a ring in the linked list, return true. Otherwise, it returns false.

Insert picture description here
Can you solve this problem with O(1) (ie, constant) memory?

Analysis:
For this problem, if there is no memory space limitation, the first thing that comes to mind is to use a hash method, use a hash storage node, and then enumerate the linked list nodes down:

If it is found to be in the hash, then it means that there is a ring and return true.
If the enumeration ends at the end, then there is no loop

Insert picture description here


But this does not meet the O(1) space complexity requirement, how should we deal with it?

If there is a loop at the end of the linked list, and if a node is enumerated later, it will continue to enumerate in a closed loop. How can it be efficiently judged that there is a loop and can be terminated quickly?

There is a ring. In fact, it is the second or third time to walk this way to say that it has a ring. A pointer cannot effectively judge whether there is a ring without using too much space in the storage state (the list may be very long, it may be already in the cycle), we can make use of the speed of the pointer (the double pointer) ah.

The core idea is to use two pointers: fast and slow. They both traverse the linked list from the head of the linked list at the same time, but the speed of the two is different . If there is a ring, it will eventually meet in the circular linked list.

In our concrete implementation, we can use fast pointers (fast) to take two steps at a time, and slow pointers (slow) to take one step at a time. If there is a ring, the fast pointer enters the ring first, and then the slow pointer enters the ring. The fast pointer will catch up with the slow pointer before the slow pointer reaches the end.

If the fast and slow pointers meet, it means there is a ring, if the fast pointer is null first, it means there is no ring.

Insert picture description here


The specific implementation code is:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
		ListNode fast=head;
		ListNode slow=fast;
		while (fast!=null&&fast.next!=null) {
		    slow=slow.next;
			fast=fast.next.next;
			if(fast==slow)
				return true;
		}
		return false;    
    }
}

Improve: find the entrance to the ring

Given a linked list, return the first node where the linked list starts to enter the loop. If the linked list has no rings, null is returned.

In order to represent the rings in a given linked list, we use the integer pos to indicate the position where the end of the linked list is connected to the linked list (the index starts from 0). If pos is -1, then there is no ring in the linked list. Note that pos is only used to identify the ring, and will not be passed to the function as a parameter.

Note: It is not allowed to modify the given linked list.

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

This question is a bit more difficult than the previous one, because if the linked list is in a loop, you need to find the entrance.

analysis:

If you don't consider memory usage, I will definitely consider hashing first, save the node and then if it appears a second time, it means that there is a loop and return directly. The implemented code is also very simple, and you can use this method if you are desperate:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        int pos=-1;
        Map<ListNode,Integer>map=new HashMap<ListNode, Integer>();
        ListNode team=head;
        while (team!=null)
        {
            if(map.containsKey(team)){
                pos=map.get(team);
                return team;
            }
            else 
                map.put(team,++pos);
            team=team.next;
        }
        return null;
    }
}

But how to use O(1) space complexity to complete this operation? The idea of ​​the above question is to use fast and slow pointers to determine whether there is a ring, but how to lock the entry of the ring?

This question looks like an algorithm question, but it is actually a mathematical reasoning question. The key to this question is also the speed indicator, but more details are needed .

Recall the details that quick and slow pointers can dig out:

Knowing that the slow pointer has taken x steps and the fast pointer has taken 2x steps, but only knowing these two conditions can not derive anything, we can only perform some operations in O(1) methods. But the difference between the speed pointer and the previous one is that we start counting with a head node.

What else can we do?

Now that we know that the point we met is inside the ring, we can use a new node to enumerate a circle to see how long the ring is!

Here, we can know the number of fast steps 2x, the number of slow steps x, and the ring length y.

Insert picture description here


We know that the slow pointer enters the ring for the first time, but the fast pointer may have walked several times, but the number of steps must be an integer multiple of the ring (otherwise it is impossible to meet at the same position).

It can be obtained quickly slow pointer number of steps = the number of fingers rings length + n steps . Of course, I don’t know how much it is. Converted into a formula, that is, 2x=x+ny and eliminate one x to get: x=ny .

In the above figure, I also mark that the faster pointer moves more than an integer number of turns. The difficulty lies here and needs to be worked around:
the x of the fast pointer is an integer multiple of the ring length y n, and the x of the slow pointer is also an integer multiple of the ring length y n.

Insert picture description here


So what's the use of this?
If a node starts from the starting point and walks to the fast, slow meeting point, it takes x steps (n*y steps). At this point, if a pointer starts from the intersection of fast and slow, if it travels an integral multiple of the loop length, it will still be in the original position.

Insert picture description here

That is to say, starting from the head node team1 by taking x steps, from the fast and slow junction node team2 taking x steps, they will eventually reach the fast and slow junction node, but on the way of enumeration, once the team1 node traverses into the ring, Then it coincides with the team2 node, so once they are equal, it will be the first point of intersection.

Insert picture description here

The implementation code is:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
	    boolean isloop=false;
		ListNode fast=new ListNode(0);//头指针
		ListNode slow=fast;
		fast.next=head;
		if(fast.next==null||fast.next.next==null)
			return null;
		while (fast!=null&&fast.next!=null) {
			fast=fast.next.next;
			slow=slow.next;
			if(fast==slow)
			{
				isloop=true;
				break;
			}
		}
		if(!isloop)//如果没有环返回
			return null;
		ListNode team=new ListNode(-1);//头指针 下一个才是head
		team.next=head;
		while (team!=fast) {
			team=team.next;
			fast=fast.next;
		}
		return team;
    }
}

Conclusion

At this point, the problem of finding the link in the linked list is solved. The code analysis may not be well written. Please point out any problems and make persistent efforts! Come on!

About the author: bigsai is mainly dedicated to the sharing of knowledge of Java, data structures and algorithms. There is an original public account of the same name:, the bigsaifirst time to harvest dry goods!