1. 소개
단일 연결 List은 널 참조로 끝나는 연결된 노드의 시퀀스입니다 . 그러나 일부 시나리오에서는 마지막 노드가 이전 노드를 가리킬 수 있으므로 효과적으로주기를 생성합니다.
대부분의 경우 우리는 이러한주기를 감지하고 인식 할 수 있기를 원합니다. 이 기사에서는주기를 감지하고 잠재적으로 제거하는 것에 초점을 맞 춥니 다.
2. 사이클 감지
이제 연결 List에서주기 를 감지 하는 몇 가지 알고리즘을 살펴 보겠습니다 .
2.1. Brute Force – O (n ^ 2) 시간 복잡성
이 알고리즘을 사용하면 두 개의 중첩 루프를 사용하여 List을 순회합니다. 외부 루프에서 우리는 하나씩 순회합니다. 내부 루프에서 우리는 헤드에서 시작하여 그 시간까지 외부 루프가 횡단하는만큼의 노드를 횡단합니다.
외부 루프가 방문한 노드를 내부 루프가 두 번 방문하면 사이클이 감지 된 것입니다. 반대로, 외부 루프가 List 끝에 도달하면 순환이 없음을 의미합니다.
public static <T> boolean detectCycle(Node<T> head) {
if (head == null) {
return false;
}
Node<T> it1 = head;
int nodesTraversedByOuter = 0;
while (it1 != null && it1.next != null) {
it1 = it1.next;
nodesTraversedByOuter++;
int x = nodesTraversedByOuter;
Node<T> it2 = head;
int noOfTimesCurrentNodeVisited = 0;
while (x > 0) {
it2 = it2.next;
if (it2 == it1) {
noOfTimesCurrentNodeVisited++;
}
if (noOfTimesCurrentNodeVisited == 2) {
return true;
}
x--;
}
}
return false;
}이 접근 방식의 장점은 일정한 양의 메모리가 필요하다는 것입니다. 단점은 큰 List이 입력으로 제공 될 때 성능이 매우 느리다는 것입니다.
2.2. 해싱 – O (n) 공간 복잡성
이 알고리즘을 사용하여 이미 방문한 노드 집합을 유지합니다. 각 노드에 대해 세트에 존재하는지 확인합니다. 그렇지 않은 경우 세트에 추가합니다. 세트에 노드가 있다는 것은 이미 해당 노드를 방문했음을 의미하며 List에주기가 있음을 나타냅니다.
세트에 이미 존재하는 노드를 발견하면주기의 시작을 발견했을 것입니다. 이를 발견 한 후에 는 아래에 설명 된 것처럼 이전 노드 의 다음 필드를 null 로 설정하여 쉽게주기를 중단 할 수 있습니다 .
public static <T> boolean detectCycle(Node<T> head) {
if (head == null) {
return false;
}
Set<Node<T>> set = new HashSet<>();
Node<T> node = head;
while (node != null) {
if (set.contains(node)) {
return true;
}
set.add(node);
node = node.next;
}
return false;
}이 솔루션에서는 각 노드를 한 번 방문하여 저장했습니다. 이는 O (n) 시간 복잡도와 O (n) 공간 복잡도에 해당하며, 평균적으로 큰 List에는 적합하지 않습니다.
2.3. 빠르고 느린 포인터
주기를 찾는 다음 알고리즘 은 은유를 사용하여 가장 잘 설명 할 수 있습니다 .
두 사람이 경주하는 경마장을 생각해보십시오. 두 번째 사람의 속도가 첫 번째 사람의 두 배라는 점을 감안할 때 두 번째 사람은 첫 번째 사람보다 두 배 빠른 속도로 트랙을 돌고 랩 시작시 첫 번째 사람을 다시 만날 것입니다.
여기서는 느린 반복기와 빠른 반복기 (2 배속)를 사용하여 List을 동시에 반복하는 유사한 접근 방식을 사용합니다. 두 반복자가 루프에 들어가면 결국 한 지점에서 만나게됩니다.
따라서 두 반복자가 어느 지점에서든 만나면주기를 발견했다고 결론을 내릴 수 있습니다.
public static <T> CycleDetectionResult<T> detectCycle(Node<T> head) {
if (head == null) {
return new CycleDetectionResult<>(false, null);
}
Node<T> slow = head;
Node<T> fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return new CycleDetectionResult<>(true, fast);
}
}
return new CycleDetectionResult<>(false, null);
}여기서 CycleDetectionResult 는 결과를 저장하는 편리한 클래스입니다. 사이클이 있는지 여부와 존재하는지 여부를 나타내는 부울 변수 인 경우 여기에는 사이클 내 회의 지점에 대한 참조도 포함됩니다.
public class CycleDetectionResult<T> {
boolean cycleExists;
Node<T> node;
}이 방법은 'The Tortoise and The Hare Algorithm'또는 'Flyods Cycle-Finding Algorithm'이라고도합니다.
3. List에서주기 제거
사이클을 제거하는 몇 가지 방법을 살펴 보겠습니다. 이 모든 방법은 'Flyods Cycle-Finding Algorithm'이주기 감지에 사용되었으며 그 위에 구축되었다고 가정합니다.
3.1. 무차별 대입
빠른 반복기와 느린 반복기가주기의 한 지점에서 만나면 반복기를 하나 더 가져와 (예 : ptr ) List의 선두를 가리 킵니다. ptr로 List을 반복하기 시작합니다. 각 단계 에서 회의 지점에서 ptr 에 도달 할 수 있는지 확인합니다 .
이것은 ptr 이 루프의 시작 지점에 도달하면 종료됩니다. 그 이유는 그것이 루프에 들어 서면 만나는 지점에서 도달 할 수있는 첫 번째 지점이기 때문입니다.
루프의 시작 ( bg )이 발견되면주기의 끝 (다음 필드가 bg를 가리키는 노드)을 찾는 것은 간단합니다 . 이 끝 노드의 다음 포인터 는 순환을 제거 하기 위해 null 로 설정됩니다 .
public class CycleRemovalBruteForce {
private static <T> void removeCycle(
Node<T> loopNodeParam, Node<T> head) {
Node<T> it = head;
while (it != null) {
if (isNodeReachableFromLoopNode(it, loopNodeParam)) {
Node<T> loopStart = it;
findEndNodeAndBreakCycle(loopStart);
break;
}
it = it.next;
}
}
private static <T> boolean isNodeReachableFromLoopNode(
Node<T> it, Node<T> loopNodeParam) {
Node<T> loopNode = loopNodeParam;
do {
if (it == loopNode) {
return true;
}
loopNode = loopNode.next;
} while (loopNode.next != loopNodeParam);
return false;
}
private static <T> void findEndNodeAndBreakCycle(
Node<T> loopStartParam) {
Node<T> loopStart = loopStartParam;
while (loopStart.next != loopStartParam) {
loopStart = loopStart.next;
}
loopStart.next = null;
}
}안타깝게도이 알고리즘은 List이 크고주기가 큰 경우에도 성능이 좋지 않습니다.주기를 여러 번 통과해야하기 때문입니다.
3.2. 최적화 된 솔루션 – 루프 노드 계산
먼저 몇 가지 변수를 정의 해 보겠습니다.
- n = List의 크기
- k = List의 선두에서 사이클 시작까지의 거리
- l = 사이클의 크기
이러한 변수 사이에는 다음과 같은 관계가 있습니다.
k + l = n
이 접근 방식에서이 관계를 활용합니다. 특히, List의 시작에서 시작하는 반복자가 이미 l 개의 노드를 이동 한 경우 List의 끝에 도달하려면 k 개의 노드를 더 이동 해야합니다.
알고리즘의 개요는 다음과 같습니다.
- 빠르고 느린 반복기가 만나면주기의 길이를 찾으십시오. 이 작업은 첫 번째 포인터에 도달 할 때까지 반복기 중 하나를 제자리에 유지하면서 다른 반복기를 계속 (정상 속도로 하나씩 반복)하여 방문한 노드 수를 유지함으로써 수행 할 수 있습니다. 이것은 l로 계산됩니다.
- List의 시작 부분에 두 개의 반복기 ( ptr1 및 ptr2 )를 사용하십시오. 반복기 ( ptr2 ) l 단계 중 하나 이동
- 이제 루프의 시작 부분에서 만날 때까지 두 반복자를 반복 한 다음 순환의 끝을 찾아 null을 가리 킵니다.
이는 ptr1 이 루프에서 k 단계 떨어져 있고, l 단계 만큼 전진하는 ptr2 도 루프의 끝에 도달하기 위해 k 단계가 필요 하기 때문에 작동합니다 ( n – l = k ).
다음은 간단하고 잠재적 인 구현입니다.
public class CycleRemovalByCountingLoopNodes {
private static <T> void removeCycle(
Node<T> loopNodeParam, Node<T> head) {
int cycleLength = calculateCycleLength(loopNodeParam);
Node<T> cycleLengthAdvancedIterator = head;
Node<T> it = head;
for (int i = 0; i < cycleLength; i++) {
cycleLengthAdvancedIterator
= cycleLengthAdvancedIterator.next;
}
while (it.next != cycleLengthAdvancedIterator.next) {
it = it.next;
cycleLengthAdvancedIterator
= cycleLengthAdvancedIterator.next;
}
cycleLengthAdvancedIterator.next = null;
}
private static <T> int calculateCycleLength(
Node<T> loopNodeParam) {
Node<T> loopNode = loopNodeParam;
int length = 1;
while (loopNode.next != loopNodeParam) {
length++;
loopNode = loopNode.next;
}
return length;
}
}다음으로 루프 길이를 계산하는 단계를 제거 할 수있는 방법에 중점을 둡니다.
3.3. 최적화 된 솔루션 – 루프 노드를 계산하지 않음
빠른 포인터와 느린 포인터가 이동 한 거리를 수학적으로 비교해 봅시다.
이를 위해 몇 가지 변수가 더 필요합니다.
- y =주기의 시작에서 볼 때 두 반복기가 만나는 지점의 거리
- z = 사이클의 끝에서 볼 때 두 반복기가 만나는 지점의 거리 (이는 l – y 와도 같습니다 )
- m = 느린 반복기가주기에 들어가기 전에 빠른 반복기가주기를 완료 한 횟수
다른 변수를 이전 섹션에서 정의한 것과 동일하게 유지하면 거리 방정식은 다음과 같이 정의됩니다.
- 느린 포인터로 이동 한 거리 = k (머리에서 사이클 거리) + y (사이클 내부의 만남 지점)
- 빠른 포인터가 이동 한 거리 = k (헤드에서 사이클 거리) + m (느린 포인터가 들어가기 전에 빠른 포인터가 사이클을 완료 한 횟수) * l (사이클 길이) + y (사이클 내부의 만남 지점)
빠른 포인터가 이동 한 거리가 느린 포인터의 두 배라는 것을 알고 있습니다.
k + m * l + y = 2 * (k + y)
다음과 같이 평가됩니다.
y = m * l – k
l 에서 양쪽을 빼면 :
l – y = l – m * l + k
또는 동등하게 :
k = (m – 1) * l + z (여기서 l – y는 위에 정의 된 z입니다)
이로 인해 :
k = (m – 1) 전체 루프 실행 + 추가 거리 z
즉, List의 선두에 하나의 반복자를 유지하고 회의 지점에 하나의 반복자를 유지하고 동일한 속도로 이동하면 두 번째 반복자는 루프를 따라 m – 1 사이클을 완료 하고 첫 번째 포인터를 만나게됩니다. 주기가 시작될 때. 이 통찰력을 사용하여 알고리즘을 공식화 할 수 있습니다.
- 루프를 감지하려면 'Flyods Cycle-Finding Algorithm'을 사용하십시오. 루프가있는 경우이 알고리즘은 루프 내부의 한 지점에서 종료됩니다 (이를 회의 지점이라고 함).
- 두 개의 반복자를 가져옵니다. 하나는 List의 맨 위에 있고 ( it1 ), 다른 하나는 회의 지점 ( it2 )에 있습니다.
- 동일한 속도로 두 반복자를 트래버스합니다.
- 헤드에서 루프까지의 거리가 k (위에 정의 된대로)이므로 헤드에서 시작된 반복기는 k 단계 후에 사이클에 도달 합니다.
- 에서는 유전율 같이, 반복자 IT2가 통과 할 1 - m 루프 사이클 여분 거리 Z를. 이 포인터는 이미 사이클 시작에서 z 거리에 있었 으므로이 추가 거리 z를 횡단하면 사이클 시작시에도 포인터를 가져옵니다.
- 두 반복자는주기의 시작에서 만나고, 이후에주기의 끝을 찾아 null을 가리킬 수 있습니다.
다음과 같이 구현할 수 있습니다.
public class CycleRemovalWithoutCountingLoopNodes {
private static <T> void removeCycle(
Node<T> meetingPointParam, Node<T> head) {
Node<T> loopNode = meetingPointParam;
Node<T> it = head;
while (loopNode.next != it.next) {
it = it.next;
loopNode = loopNode.next;
}
loopNode.next = null;
}
}이것은 연결 List에서주기를 감지하고 제거하는 데 가장 최적화 된 접근 방식입니다.
4. 결론
이 기사에서는 List에서주기를 감지하는 다양한 알고리즘에 대해 설명했습니다. 컴퓨팅 시간과 메모리 공간 요구 사항이 다른 알고리즘을 조사했습니다.
마지막으로 'Flyods Cycle-Finding Algorithm'을 사용하여 감지 된주기를 제거하는 세 가지 방법도 보여주었습니다.
전체 코드 예제는 Github에서 사용할 수 있습니다 .