다른 노드를 참조하는 연결된 목록에서 노드를 찾는 방법

Question

10 개의 노드와 6 번째 노드로 연결된 목록이 두 번째 노드를 가리키는 경우. 루프가 내부에 있는지 확인할 수있는 방법

Answer 1

노드가 10 개이면 링크 된 목록에서 마지막 노드가 null이어야하기 때문에 이런 상황은 발생할 수 없습니다. 위에서 말했듯이이 상황에서는 5 번째 노드가 null이어야하고 5 개의 요소 만 있습니다. 당신이 원형 연결리스트를 사용하는 경우에 당신은 가장 유명한이 "토끼와 거북이"알고리즘 (일명 플로이드의 사이클 탐지)는 몇 가지 흥미로운 cycle detection 알고리즘이있다

'(last->data== (first++)->data)' 

Answer 2

확인할 수 있습니다. 토끼가 거북이를 두 배나 빨리 걷는다면주기가 있으면 다시 만나게 될 것이라는 생각에 기반합니다.

브렌트의 알고리즘은 좀 더 복잡하지만 "다음" 함수의 평가는 더 적습니다 (여기에는 포인터가 더 적습니다).

더 적은 수의 평가를 사용할 수있는 방법이 있습니다. 내가 아는 한 모든 것은 더 많은 스토리지를 사용하는 것을 기본으로합니다. 가장 확실한 방법은 "지금까지 본 노드"의 해시 테이블을 유지하고 이미 노드가있는 노드를 추가 할 때주기를 감지하여 두 번째로 볼 노드를 즉시 감지하는 것입니다 그러나 O (n) 공간을 취한다. Gosper's loop detection 알고리즘은 O (log n) 공간 만 사용하며 훨씬 더 흥미 롭습니다 (아마도 약간 이해하기 힘들 것입니다). multiple stacks을 사용하여 튜너 블 (공간 대 평가) 알고리즘을 사용합니다 (기사에는 더 많은 알고리즘에 대한 링크가 포함되어 있습니다).