연결된 목록의 루프 검색

단일 포인터 만 사용하여 연결된 목록의 루프를 검색하는 방법은 무엇입니까? (느슨하고 빠른 포인터 (토끼 및 거북이) 원하지 않음)연결된 목록의 루프 검색

출처

2011-10-09 Ashish Anand

해답이 거북이 및 거북이 알고리즘 인 경우 꽤 인공적인 질문이었을 것입니다. –

"하나의 포인터 만 사용 하시겠습니까?" 이미 목록의 머리 부분에 대한 포인터를 저장하는 하나의 포인터를 사용합니다. 그 포인터가 아닌 다른 포인터를 만들 수 있습니까? – templatetypedef

@templatetypedef : 두 개의 포인터는 링크 된 목록을 방문하는 두 개의 포인터 만 의미 할 수 있습니다. – false

추가 O (N) 메모리가 마음에 들지 않는다면 연결된 목록을 따라 가면서 방문한 노드를 저장할 수 있습니다. .

각 노드에서 노드가 이미 해시 테이블에 존재하는지 확인합니다. 그렇다면 루프를 찾았습니다. 그렇지 않으면 해시 테이블에 추가하고 다음 노드로 이동합니다.

출처

2011-10-09 19:06:08 MAK

하지만 여러 포인터 (해시 테이블에 저장된 각 노드에 하나씩)가 필요하지 않습니까? – templatetypedef

@templatetypedef : True. 나는 "하나의 포인터 사용하기"라는 의미로 하나의 포인터를 사용하여 두 개의 포인터를 사용하는 대신 목록을 반복하는 방법을 사용합니다. 이것은 반복을 위해 하나의 포인터를 사용하지만, 우리는 여전히 방문한 모든 노드에 대한 포인터를 저장하고 있습니다. 따라서 제가 대답에서 언급 한 O (n) 메모리입니다. 나는 OP가 그것으로 잘 될지도 모른다라고하는 것이라고 상상했다. – MAK

노드가 값과 다음 노드에 대한 포인터로 구성된 경우 첫 번째 노드에 대한 포인터를 만드는 목록을 사용할 수 있습니다. 포인터가 첫 번째 노드에 대한 포인터와 동일한 값을 가지면 모든 노드에서 확인할 수 있습니다.

출처

2011-10-09 19:11:51

사이클이 정면이 아닌 목록 가운데로 되돌아 가면 어떻게 될까요? – templatetypedef

Brent's algorithm이 분명히 여기에 있습니다 : 루프가없는 목록의 경우 플로이드의 거북이와 토끼가 노드의 절반을 다시 방문해야하지만 목록을 한 번 방문하면됩니다. 루프가있는 목록의 경우 플로이드보다 루프에서 "회전"하지 않습니다. Floyd가 많은 것을 필요로 할 때 가장 좋은 경우에는 단 하나의주기가 필요합니다. 길이가 긴 루프가없는 시퀀스와 길이가 1 인 루프를 생각해보십시오.이 경우 브렌트의 경우 루프를 한 번 방문한 후주기를 감지하여 각 노드를 정확히 한 번 방문하는 것이 가장 좋습니다. Floyd는 각 노드를 평균 세 번 방문해야합니다.

기본 아이디어는 링크 된 목록을 방문하여 현재 노드의 포인터를 이미 방문한 노드와 비교하는 것입니다. 즉, 방문한 노드 당 하나의 포인터 비교입니다. 포인터는 간단한 논리에 따라 때때로 업데이트됩니다.

출처

2013-01-07 00:53:13 false

두 개의 포인터가 필요하지 않습니까? – templatetypedef

@templatetypedef : 하나의 포인터 만 링크 된 목록을 탐색합니다. 다른 하나는 때때로 첫 번째 값으로 설정됩니다. – false

연결된 목록의 루프 검색

답변

관련 문제