PHP 및 Go에서 순환 연결 목록을 감지하는 방법-PHP 문제-php.cn

PHP 및 Go에서 순환 연결 목록을 감지하는 방법

醉折花枝作酒筹

풀어 주다： 2023-03-11 20:42:01

앞으로

1937명이 탐색했습니다.

링크드 리스트의 링 진입 노드 문제는 면접에서든, 대학원 입시 과정에서든 매우 고전적인 질문입니다. 일반적으로 받아들여지는 해결책은 이중 포인터(빠른 포인터와 느린 포인터)의 해결책입니다. 물론 이것은 오랫동안 이야기되어 왔습니다. 오늘은 그것을 소개하겠습니다.

연결된 목록이 주어졌을 때 순환 연결 목록인 경우 순환의 시작 노드를 반환하는 알고리즘을 구현하세요. 링 연결 리스트의 정의: 연결 리스트에 있는 노드의 다음 요소가 이전에 나타난 노드를 가리키는 경우 이는 연결 리스트에 순환이 있음을 나타냅니다.

문제 해결 아이디어 1

연결된 목록을 탐색하고 각 결과를 맵에 넣습니다. 반복되는 요소가 있으면 순환 연결 목록이 있습니다.

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

로그인 후 복사

문제 해결 아이디어 2

빠르고 느린 포인터 솔루션: 우리는 두 가지를 정의하십시오. 손은 빠르고 꽉 차 있습니다. 느린 포인터는 한 번에 한 단계만 이동하고, 빠른 포인터는 한 번에 두 단계만 이동합니다. 처음에는 느린 포인터가 head 위치에 있고 빠른 포인터가 head.next 위치에 있습니다. 이처럼 이동 중에 빠른 포인터가 느린 포인터를 따라잡는다면 연결리스트는 원형 연결리스트라는 뜻이다. 그렇지 않으면 빠른 포인터가 연결 목록의 끝에 도달하게 되고 연결 목록은 순환 연결 목록이 아닙니다.

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

로그인 후 복사

위 내용은 PHP 및 Go에서 순환 연결 목록을 감지하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!