Linked list whether there is a ring problem seems to be simple, but there are a lot of actual processing need to pay attention to, this problem is very high frequency written interview questions, memory is not firm easy to forget, you can take a look at learning a wave! A friend of mine met her at a job interview.

Java advanced interview, SSM framework, distributed architecture, micro services, high concurrency, algorithms, etc., now free to share to read this article Java programmer friends, need to get their own

Java Basics – Intermediate – Advanced interview +SSM framework + distributed + performance tuning + microservices + concurrent programming + network + design patterns + data structures and algorithms

Check whether the list has rings

Given a linked list, determine whether there are rings in the list.

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.

Returns true if there are rings in the list. Otherwise, return false.

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

For this problem, if there is no memory space limit, the first thought is to use the hash method, use a hash storage node, and then enumerate the list nodes down:

If any of these are found in the hash, then the ring returns true. If the enumeration ends at the end, there is no ring

But this does not satisfy the O(1) space complexity requirements, what should we do?

If there is a loop at the end of the list, and if a node enumerates in a closed loop, how can it be efficiently identified and quickly terminated?

There is a ring, in fact, the second time, the third time through the road to say that it has a ring, a pointer in the state of not using too much space storage can not effectively determine whether there is a ring (may be a long list, may have been in the loop), we can use the fast and slow pointer (double pointer) ah.

The core idea is to use two Pointers: fast and slow, which traverse the linked list from the head of the list at the same time, but at different speeds. If there are loops, they will eventually meet in the circular list.

We can implement fast two steps at a time and slow one step at a time. If there is a ring, the fast pointer enters the ring first, the slow pointer enters the ring later, and the fast pointer catches up with the slow pointer before the slow pointer reaches the end.

If the fast and slow Pointers meet, then there is a loop. If the fast Pointers are null first, then there is no loop.

The specific implementation code is as follows:

/** * 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; }}Copy the code

Raise: Find the entrance to the ring

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.

Note: Modification of a given linked list is not allowed.

Can you use O(1) space to solve this problem?

This is a little bit harder than the last one, because if the list is looped, you have to find the entry point.

Analysis:

If memory usage is not a consideration, I would definitely consider hash first, storing the node and then returning it if it occurs a second time. The implementation code is also very simple, desperate can use this method:

/**
 * 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;
    }
}
Copy the code

But how do you do this with the space complexity of O(1)? How do you lock the entry of the ring?

This looks like an algorithm problem, but it’s actually a mathematical reasoning problem. The key here is also the speed pointer, but you need to dig into more detail.

Recall the details that the fast and slow Pointers can dig up:

We know that the slow pointer has taken x steps and the fast pointer has taken 2x steps, but just knowing these two conditions doesn’t give us anything, and the only thing we can do is do something with order one. But what’s a little different about this is that we started the count with a head node.

What else can we do?

Now that we know that the point we meet is inside the ring, we can use a new node to go through the circle and see what the length of the ring is. Wow!

In this, we can know the number of steps taken by fast 2x, the number of steps taken by slow x, and the ring length y.

We know that the slow Pointers are entering the loop for the first time, but the fast Pointers may have walked several times, but the extra steps must be an integer multiple of the loop (otherwise they cannot meet in the same position).

Then we can get fast pointer steps = slow pointer steps +n ring length. And of course n here I don’t know what it is right now. And if you look at the formula, 2x is equal to x plus ny and you cancel out an x and you get x is equal to ny.

I’ve also indicated in the graph above that the fast pointer that goes too far is the integer number of turns. The difficulty lies in this, which requires flexibility:

The fast pointer’s extra x is an integer multiple of ring length y, and the slow pointer’s extra X is an integer multiple of ring length y.

So what does that do? If a node starts from the starting point, it takes x (n*y) steps to reach the intersection of fast and slow. At this point, if a pointer starts at the intersection of fast and slow and goes an integer multiple of the length of the loop, it will still be there.

That is to say, from the beginning of head node team1 take x steps, from the fast and slow intersection node team2 take X steps, they still finally reach the fast and slow intersection node, but in the process of enumeration, once team1 node traverses into the ring, it will overlap with Team2 node. So once they’re equal that’s the first point where they meet.

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 if there is no loop; ListNode team=new ListNode(-1); Head team. Next =head; while (team! =fast) { team=team.next; fast=fast.next; } return team; }}Copy the code

conclusion

Here, linked list to find the ring problem is solved, code analysis may not write good enough, there is a problem also please point out, make persistent efforts! Come on!