This is the fifth day of my participation in the August More text Challenge. For details, see:August is more challenging

Topic Description:

141. Ring Linked List – Force Link (LeetCode) (leetcode-cn.com)

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 continuously tracing the next pointer, there is a loop in the list. To represent the loop in a given list, we use the integer POS to represent where the end of the list is joined into the list (the index starts at 0). If pos is -1, there are no rings in the list. Note: POS is not passed as a parameter, only to identify the actual condition of the linked list.

Returns true if there is a loop in the list. Otherwise, return false.

Advanced:

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

The sample a

Input: head = [3,2,0,-4], pos = 1 output: trueCopy the code

Example 2

Input: head = [1,2], pos = 0 output: true explanation: there is a loop in the list with the end connected to the first node.Copy the code

Example 3

Input: head = [1], pos = -1 Output: false Description: There is no loop in the linked list.Copy the code

Thought analysis

Node counting

The easiest thing is to go through the list, loop through each list, put it in a HashSet, and take advantage of the fact that hashsets are not repeatable, so if we fail to add a node, that node has been added before, so there’s a loop, and otherwise there’s no loop.

AC code

class Solution {
    fun hasCycle(head: ListNode?).: Boolean {
        val set = mutableSetOf<ListNode>()
        var p = head
        while (null! = p) {if (!set.add(p)) {
                return true
            }
            p = p.next
        }
        return false}}Copy the code

How fast a pointer

To determine if there is a loop in the list, we can define a slow pointer that points to the head node of the list and a fast pointer that points to the next node of the list. Then, slow moves forward one position at a time, and fast moves forward two positions at a time. In this way, if there is a loop in the list, the fast pointer will enter the loop first and then catch up with the slow pointer.

For specific ideas, please refer to the animation demonstration in this problem solution:

AC code

class Solution {
    fun hasCycle(head: ListNode?).: Boolean {
        if (null == head || null== head? .next) {return false
        }
        var slow = head
        varfast = head? .nextwhile(slow ! = fast) {if (null == fast || null== fast? .next) {return false} slow = slow? .next fast = fast? .next? .next }return true}}Copy the code

conclusion

From official explanation:

“Floyd Loop determination algorithm” (also known as the tortoise and rabbit race algorithm)

Imagine a tortoise and a hare moving on a linked list, with the hare running fast and the tortoise running slow. When the tortoise and the hare start moving from the same node on the list, if there is no ring in the list, the hare will always be in front of the tortoise; If there are rings in the list, the “rabbit” enters the ring before the “turtle” and moves within the ring all the time. Wait until “tortoise” when entering a ring, because “rabbit” speed is fast, it can meet with tortoise certainly in a certain moment, namely set “tortoise” several laps.

We can solve the problem according to the above ideas. Specifically, we define two Pointers, one near and one full. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. Initially, the slow pointer is at position head and the fast pointer at position head.next. In this way, if in the process of moving, the fast pointer in turn catch up with the slow pointer, the list is circular. Otherwise the fast pointer will reach the end of the list, which is not a circular list.

If we knew the algorithm, then the advanced answer would be solved.

reference

Ring Linked List – Ring linked list – Force link (LeetCode) (leetcode-cn.com)

#141 Ring linked List – Ring linked list – force button (leetcode-cn.com)

Further reading

This article deals with common linked list problems (welcome exchange – ring linked list – force buckle (LeetCode) (leetcode-cn.com)