The title information

Subject address: leetcode-cn.com/problems/li…

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. 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: POS is not passed as an argument, just to identify the actual state of the linked list.

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

Advanced:

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

Example 1:

Enter: head = [3.2.0, -4], pos = 1Output:trueExplanation: A linked list has a ring whose tail is connected to a second node.Copy the code

Example 2:

Enter: head = [1.2], pos = 0Output:trueExplanation: A linked list has a ring whose tail is connected to the first node.Copy the code

Example 3:

Enter: head = [1], pos = -1Output:falseExplanation: There are no rings in the linked list.Copy the code

Tip:

The number of nodes in the list ranges from [0, 104] -105 <= node. val <= 105 pos is -1 or a valid index in the list.

Solution 1: fast or slow pointer

This problem is directly associated with the fast and slow pointer, a road two people running a fast and slow, if there is no ring will never catch up, there are rings will meet. Something like this (one slow step, two fast steps) :

The code is as follows:

public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while(fast ! =null&& fast.next ! =null) {
    	// Start with the same starting point, so go first and then judge whether it is equal
        slow = slow.next;
        fast = fast.next.next;
        if (slow.equals(fast)) {
            return true; }}return false;
}
Copy the code

The space complexity doesn’t have to be order one.

In time, if the number of times is less than half, fast will be empty. If there are the most loops, FAST will complete one more time. In general, O (n)

Solution 2: Hash table

This kind of circular problem starts with fast or slow hands, not in other directions. The fast and slow Pointers are of course optimal, but familiarize yourself with other containers. The same as before, the condition of using container storage to judge whether the ring is formed is that it has been saved before the node appears in the process of continuous next storage. So you can count with hashMap but only if it happens twice so you can just use set

public boolean hasCycle(ListNode head) {
    Set<ListNode> set = new HashSet();
    while(head ! =null) {
        if(! set.add(head))return true;
        head = head.next;
    }
    return false;
}
Copy the code

First of all, it’s necessary to iterate over it in time O(n), space O(n) for each node in a hash table.

conclusion

And that’s done. So that’s the end of the list chapter in the elementary algorithm collection. There are six problems that are really easy. Through these days to complete the six questions or to the linked list such data structure is familiar with a lot, learned a variety of basic operations. Another point that you may need to be familiar with and think about is the positioning of various scenarios through dual-pointer linked list operations (such as locating the last node in the front, locating the middle node in the list, etc.). Next, start tree related algorithms.