[leetcode] 13. linked list cycle · circular linked list

Title Description

Description in English

Given head, the head of a linked list, determine if the linked list has a cycle in it. 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. Note that pos is not passed as a parameter. Return true if there is a cycle in the linked list. Otherwise, return false.

English address

https://leetcode.com/problems/linked-list-cycle/

Description of Chinese version

Give you a list of the head node head , Judge whether there are links in the list . If there is a node in the linked list , It can be done by continuously tracking next The pointer reaches again , Then there is a ring in the linked list . To represent a ring in a given list , The evaluation system uses an integer pos To indicate where the end of the list is connected to the list （ Index from 0 Start ）.

Be careful ：pos Not passed as an argument . Just to identify the actual situation of the linked list . If there are rings in the list , Then return to true . otherwise , return false .

Example 1：

​ Input ：head = [3,2,0,-4], pos = 1 Output ：true explain ： There is a link in the list , Its tail is connected to the second node .

Example 2：

Input ：head = [1,2], pos = 0 Output ：true explain ： There is a link in the list , Its tail is connected to the first node .

Example 3：

​

Input ：head = [1], pos = -1 Output ：false explain ： There are no links in the list .

Tips ：

• The number range of nodes in the linked list is [0, 104]

• -105 <= Node.val <= 105

• pos by -1 Or one of the lists Valid index

Address of Chinese version

https://leetcode.cn/problems/linked-list-cycle/

Their thinking

One by one , newly build Map<NodeList, Interger> For storage path NodeList,Map Add what is not in , If you have something, go back true, There are repeated elements until the end of traversal , Just go back to false

How to solve the problem

My version

/**
 * 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) {
        Map<ListNode, Integer> map = new HashMap<>();
        int index = 0;
        while (head != null) {
            if (map.containsKey(head)) {
                return true;
            } else {
                map.put(head, index);
                index++;
                head = head.next;
            }
        }

        return false;
    }
}

​

Official edition

Method 1 ： Hashtable

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> seen = new HashSet<ListNode>();
        while (head != null) {
            if (!seen.add(head)) {
                return true;
            }
            head = head.next;
        }
        return false;
    }
}

Method 2 ： Speed pointer

​

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}