How to detect cycle linked lists in PHP and Go

The problem of the entry node of the ring in the linked list is a super classic question, whether it is in an interview or in the process of postgraduate entrance examination. The generally accepted solution is the solution of double pointers (fast and slow pointers). Of course, this has been talked about for a long time. Today we will introduce it.

Given a linked list, if it is a cyclic linked list, implement an algorithm to return the starting node of the cycle. The definition of a ring linked list: If the next element of a node in the linked list points to the node that appeared before it, it indicates that there is a cycle in the linked list.

Solution idea 1

Traverse the linked list and put each result into the map. If there are repeated elements, there is a circular linked list

/** 
* Definition for singly-linked list. 
* type ListNode struct { 
* Val int * Next *ListNode 
* } 
*/
func detectCycle(head *ListNode) *ListNode {
    visited := make(map[*ListNode]struct{}, 1)
    work := head

    for work != nil {
        _, ok := visited[work]
        if ok {
            return work
        } else {
            visited[work] = struct{}{}
        }
        work = work.Next
    }

    return nil}

Solution to the problem Idea 2

Fast and slow pointer solution: We define two pointers, one fast and one full. The slow pointer moves only 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 is at position head.next. In this way, if the fast pointer catches up with the slow pointer during the movement, it means that the linked list is a circular linked list. Otherwise, the fast pointer will reach the end of the linked list, and the linked list is not a circular linked list.

/** 
* Definition for a singly-linked list. 
* class ListNode { 
* public $val = 0; 
* public $next = null; 
* function __construct($val) { $this->val = $val; } 
* } 
*/class Solution {
    /** 
    * @param ListNode $head * @return Boolean 
    */
    function hasCycle($head) {
        $fast = $head;
        $slow = $head;

        while ($fast != null && $fast->next != null) {
            $fast = $fast->next->next;
            $slow = $slow->next;
            if ($fast === $slow) {
                return true;
            }
        }
        return false;
    }}

Recommended: 《2021 PHP interview questions summary (collection)》《php video tutorial》

The above is the detailed content of How to detect cycle linked lists in PHP and Go. For more information, please follow other related articles on the PHP Chinese website!