연결리스트에서 순환 감지

또 다른 연결리스트 알고리즘입니다.

링크드 리스트에서 순환을 감지합니다.

사실 그렇게 나쁘지는 않습니다. O(n) 시간에 이를 수행하는 방법에는 적어도 3가지가 있습니다.

가장 쉬운 방법은 노드 방문 여부를 나타내는 플래그를 포함하도록 연결 목록 노드를 수정하는 것입니다. 목록을 순회하면서 방문한 노드를 만나면 주기가 있습니다.

또 다른 기술은 방문한 노드나 해당 노드에 대한 참조가 포함된 해시맵을 사용합니다. 목록이 순회되면서 노드 또는 해당 참조가 해시에 삽입됩니다. 해시맵에 이미 표시된 노드를 만나면 순환이 존재하는 것입니다. 이 기술에는 단일 순회만 필요하지만 해시맵으로 인해 더 많은 메모리가 필요합니다.

이번 게시물에서는 플로이드의 알고리즘을 사용하여 주기를 감지하겠습니다. 꽤 간단합니다.

func DetectCycle[T any](ll *LinkedList[T]) bool {
    slow := ll.Head
    fast := ll.Head
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
        if fast == slow {
            return true
        }
    }
    return false
}

이 기술은 목록에 2개의 포인터를 사용합니다. 목록을 탐색할 때 포인터 하나는 한 번에 한 노드씩 이동하고 다른 포인터는 한 번에 두 노드를 이동합니다. 두 포인터가 만나면 순환이 존재합니다.

이것이 작동하는 이유는 무엇입니까? 목록을 탐색하면 두 포인터 사이의 거리가 늘어납니다. 주기가 있는 경우 빠른 포인터가 느린 포인터를 '랩'합니다.

좀 더 효율적인 구현 방법이 있나요? 경계 조건이 누락되었습니까? 댓글로 알려주세요.

감사합니다!

이 게시물과 이 시리즈의 모든 게시물에 대한 코드는 여기에서 확인할 수 있습니다.

위 내용은 연결리스트에서 순환 감지의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!