여기서, 자바 세드 윅의 우수한 알고리즘에서카운트 수는 그 원형이 될 수
이 더 포함 된 단일 연결리스트의 노드에 대한 링크를 감안할 때 (Q 3.54) 문제입니다 null 링크 (즉, 각 노드는 자체 또는 다른 노드에 링크 됨)는 노드를 수정하지 않고 일정한 메모리 공간만을 사용하여 다른 노드의 수를 결정합니다.
당신은 그것을 어떻게해야합니까? 토끼와 거북이 알고리즘을 사용하여 목록을 한 번 스캔하여 원형인지 여부를 확인한 다음 다시 스캔하여 목록이 원형이되는 곳을 찾은 다음 다시 스캔하여 노드 수를이 위치로 다시 계산하십시오. 나에게 약간의 짐승 같은 소리가 들린다. 나는 훨씬 더 우아한 해결책이 있다고 생각한다.
tortoise and hare algorithm 당신에게 모두주기 길이와 노드의 수를 제공 할 수 있습니다. http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare
그것은 O (N) 시간에 실행 및 메모리의 일정 금액이 필요합니다
어디서 왔는지 그리고 동일한 노드에왔다면 끝났습니다.
은 이진 트리의 항목을 저장하는 시도하고 당신은 O를 (N의 * 로그 (N)) 시간 및 O (N) 공간 comlexity
편집
당신이 경우 로그 (N) 공간 comlexity을 사용할 수 있습니다 모든 순서를 지수 순서로 저장하지 마십시오. 즉, 1, 2, 4, 8, 16 번째 저장하고 그 다음에 계속해야한다는 것을 의미합니다. 이것에 대한 시간 comlexity는 N * 로그 (N)^2
체크 아웃이 : Puzzle: Loop in a Linked List
포인터 마킹 : 실제로 리스트 C 구조체 적어도 포인터 을 사용하여 구현된다 링크; C 내의 그러한 구조체 은 4 바이트 정렬되어야한다. 따라서 의 최하위 2 비트는 0입니다. 목록을 횡단하는 동안 이 최하위 비트를 뒤집어서 가로 지르는 포인터를 '표시'할 수 있습니다. 두 번째 탐색은 비트를 지우는 것입니다. 주기가 (각각 λ와 μ)이 시작되기 전에
"노드를 수정하지 않고 다른 노드의 수를 결정해야합니다."라는 질문이 있습니다. 이것이 요구 사항이 아니더라도이 솔루션은 구현 세부 사항에 너무 많이 의존하고 언어에 구애받지 않기 때문에 냄새가 난다. – jason
@ Jason : 누가 신경 쓰겠 니? 좀 더 많은 언어로 작동하는 * 빠른 알고리즘 (내 환경에 어울리는)을 선호합니다. 나는이 대답이 빠른 알고리즘을 묘사하는 것이 아니라, 일반적으로 알고리즘의 성능이 이식성보다 더 중요하다는 것을 말하고있다. – Artelius
@ Jason, 예. 임시 노드를 수정합니다. 어쨌든, 나는 그것이 최선의 해결책이 아니라는 것을 알고 있지만 흥미로운 것으로 생각합니다. –
가장 우아한 해결책은 플로이드의 사이클 찾는 알고리즘이다.
하하, 나는 거북이와 토끼가 만날 수있는 단계가주기 길이에 관한 정보를 제공한다는 것을 내 견해를 토대로 정교한 대답을 고안하는 중이었습니다. – Joren
나도. :(Google은 내 친구, Google은 내 친구, Google은 내 친구 ... – TonyOssa
+1.하지만 알고리즘의 시간 복잡도는 무엇입니까? 사이클 O (lambda + u)를 찾고 사이클 길이 O (λ)를 찾고, 목 길이 O (lambda * u)를 찾으십시오. N = min (lambda, u)로 가정하면 전체적으로 O (N^2)가됩니다 .2368보다 더 좋은 방법이 있습니까? – Akusete