단일 연결된 목록의주기를 감지하는 것은 잘 알려진 문제입니다. 나는이 질문이 인터넷 전체에서 수천 번 요구되었다는 것을 안다. 내가 다시 묻는 이유는 내가 다른 곳에서 만나지 못한 해결책을 생각하기 때문입니다. (나는 그것을 깊이 탐구하지 않았다는 것을 인정한다).단일 링크 된 목록의주기 검색
내 솔루션은 다음과 같습니다
일부 노드에 연결리스트 포인터를 감안할 때이 노드 사이의 연결을 해제하고 노드 -> 다음(); 그런 다음 node-> next()에서 시작하여 끝 (루프가 없음을 의미) 또는 루프에 있음을 노드에 도달 할 때까지 트래버스합니다.
위의 해결 방법에는 어떤 것이 있습니까?
참고 : 완료되면 링크에 다시 가입하십시오.
(전체 목록의 기간 즉, 사이클) 완전한 사이클을 감지하기 위해 노력할 것, 예컨대 :
A -> B -> C -> D -> A
그러나 우리는 목록에서 다른 곳주기가 있다면?
예를 들어,
A -> B -> C -> D -> E -> C
나는 알고리즘이 경우주기를 감지 것을 볼 수 없습니다.
첫 번째 사례를 감지하려면 링크를 끊을 필요가 없습니다. 우리는 목록을 탐색하고 각 노드의 next 링크를 head 요소와 계속 비교하여 처음부터 다시 시작했는지 (또는 끝까지 도달했는지) 확인할 수 있습니다.
가장 간단한 접근법 (꼭 필요한 것은 아니지만 모두 코드의 몇 줄에서 Java로 구현하는 방법을 알고 있어야 함)은 노드의 해시 세트를 작성한 다음 찾을 때까지 추가하는 것입니다. 당신이 이미 전에 본 하나. 그래도 추가 메모리가 필요합니다.
노드를 표시 할 수있는 경우 이전에 표시 한 기호를 찾을 때까지 표시를 시작하십시오 (해시 맵은 본질적으로 외부 표시 자임).
그리고 일반적인 그래프 이론 책을 확인
...당신은 당신이 다시 말을 가입하더라도 링크를 중단 할 수 없습니다. 다른 프로그램이 동시에 목록을 읽으면 어떻게 될까요?
알고리즘은 작업하는 동안 목록을 손상 시켜서는 안됩니다.
대부분의 솔루션은 두 가지 "주자"가 서로 다른 속도로 최상의 솔루션이라고 제안합니다. O (n) 일 수도 있고, 내 솔루션 O (n)도 아닙니다. –
링크를 끊을만한 이유가 보이지 않습니다. 노드를 감시 멤버로 취급하십시오. 문제 : 노드가 a 인 경우 알고리즘이 a-> b-> c-> d-> e-> c에서 작동하지 않습니다. 알고리즘은 마지막 노드가 첫 번째 노드를 가리키는 루프 만 탐지합니다. –
루프가 전역 적이 지 않으면이 작업이 수행되지 않습니다. 예 :'a -> b -> c -> b -> c -> b -> c -> b -> ... –