Bagaimana untuk mengesan senarai terpaut kitaran dalam PHP dan Go

Masalah nod kemasukan cincin dalam senarai terpaut adalah soalan super klasik, sama ada dalam temu duga atau dalam proses peperiksaan kemasukan pasca siswazah. Penyelesaian yang diterima umum ialah penyelesaian penunjuk berganda (penunjuk cepat dan perlahan, sudah tentu, ini telah dibincangkan untuk masa yang lama). Hari ini kami akan memperkenalkannya.

Memandangkan senarai terpaut, jika senarai terpaut kitaran, laksanakan algoritma untuk mengembalikan nod permulaan kitaran. Takrif senarai terpaut cincin: Jika elemen seterusnya nod dalam senarai terpaut menghala ke nod yang muncul sebelum itu, ia menunjukkan bahawa terdapat kitaran dalam senarai terpaut.

Idea penyelesaian masalah 1

Lintas senarai terpaut dan letakkan setiap hasil ke dalam peta Jika terdapat elemen berulang, terdapat senarai terpaut bulat

/** 
* 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}

. Idea penyelesaian masalah 2

Menyelesaikan penunjuk cepat dan perlahan: Kami mentakrifkan dua petunjuk, satu cepat dan satu penuh. Penunjuk perlahan bergerak hanya satu langkah pada satu masa, manakala penunjuk pantas bergerak dua langkah pada satu masa. Pada mulanya, penunjuk perlahan berada di kepala kedudukan dan penunjuk cepat berada di kepala kedudukan. seterusnya. Dengan cara ini, jika penunjuk pantas mengejar penunjuk perlahan semasa pergerakan, ini bermakna senarai terpaut ialah senarai pautan bulat. Jika tidak, penuding pantas akan sampai ke penghujung senarai terpaut dan senarai terpaut bukan senarai pautan bulat.

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

Disyorkan: "Ringkasan soalan temuduga PHP 2021 (koleksi)" "tutorial video php"

Atas ialah kandungan terperinci Bagaimana untuk mengesan senarai terpaut kitaran dalam PHP dan Go. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!