Java로 연결된 목록 구조가 있다고 가정하십시오. 노드로 구성됩니다.
class Node {
Node next;
// some user data
}각 노드는 다음 노드를 가리키는 마지막 노드를 제외하고 다음 노드를 가리 킵니다. 리스트가 루프를 포함 할 가능성이 있다고하자. 즉, 널 (null) 대신 최종 노드가리스트의 앞에있는 노드 중 하나에 대한 참조를 갖는다.
쓰는 가장 좋은 방법은 무엇입니까
boolean hasLoop(Node first)true주어진 노드가 루프가있는 목록의 첫 번째 경우 반환 하고 false그렇지 않으면? 일정한 공간과 적당한 시간이 걸리도록 어떻게 쓸 수 있습니까?
다음은 루프가있는 목록의 모습입니다.
답변
Floyd의 사이클 찾기 알고리즘 ( 거북 및 토끼 알고리즘 이라고도 함)을 사용할 수 있습니다 .
아이디어는 목록에 대한 두 개의 참조를 가지고 서로 다른 속도 로 이동하는 것 입니다. 1노드 별로 하나씩 이동하고 노드 별로 이동하십시오 2.
- 연결된 목록에 루프가 있으면 분명히 충족됩니다.
- 그렇지 않으면 두 참조 중 하나
next가null됩니다.
알고리즘을 구현하는 Java 함수 :
boolean hasLoop(Node first) {
if(first == null) // list does not exist..so no loop either
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list
while(true) {
slow = slow.next; // 1 hop
if(fast.next != null)
fast = fast.next.next; // 2 hops
else
return false; // next node null => no loop
if(slow == null || fast == null) // if either hits null..no loop
return false;
if(slow == fast) // if the two ever meet...we must have a loop
return true;
}
}답변
홀수 길이 목록을 올바르게 처리하고 선명도를 향상시키는 Fast / Slow 솔루션이 개선되었습니다.
boolean hasLoop(Node first) {
Node slow = first;
Node fast = first;
while(fast != null && fast.next != null) {
slow = slow.next; // 1 hop
fast = fast.next.next; // 2 hops
if(slow == fast) // fast caught up to slow, so there is a loop
return true;
}
return false; // fast reached null, so the list terminates
}답변
플로이드 알고리즘보다 우수
Richard Brent는 대체 사이클 감지 알고리즘을 설명했습니다. 했는데, 이것은 토끼와 거북이 [Floyd ‘s cycle]와 비슷하지만 여기서 느린 노드는 움직이지 않지만 나중에 고정 된 빠른 노드의 위치로 “텔레포트”된다는 점을 제외하고 간격.
설명은 여기에 있습니다 : http://www.siafoo.net/algorithm/11
자신의 알고리즘이 24 ~ 36 % 빠른 플로이드의 사이클 알고리즘보다 것을 브렌트 주장. O (n) 시간 복잡성, O (1) 공간 복잡성
public static boolean hasLoop(Node root){
if(root == null) return false;
Node slow = root, fast = root;
int taken = 0, limit = 2;
while (fast.next != null) {
fast = fast.next;
taken++;
if(slow == fast) return true;
if(taken == limit){
taken = 0;
limit <<= 1; // equivalent to limit *= 2;
slow = fast; // teleporting the turtle (to the hare's position)
}
}
return false;
}답변
내가 목록을 일시적으로 변경했을 때 거북이와 토끼에 대한 대안 솔루션은 그리 좋지는 않습니다.
아이디어는 목록을 걷고 가고 갈수록 뒤집는 것입니다. 그런 다음 이미 방문한 노드에 처음 도달하면 다음 포인터가 “뒤로”를 가리키며 반복이 first다시 진행 되어 종료됩니다.
Node prev = null;
Node cur = first;
while (cur != null) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
boolean hasCycle = prev == first && first != null && first.next != null;
// reconstruct the list
cur = prev;
prev = null;
while (cur != null) {
Node next = cur.next;
cur.next = prev;
prev = cur;
cur = next;
}
return hasCycle;테스트 코드 :
static void assertSameOrder(Node[] nodes) {
for (int i = 0; i < nodes.length - 1; i++) {
assert nodes[i].next == nodes[i + 1];
}
}
public static void main(String[] args) {
Node[] nodes = new Node[100];
for (int i = 0; i < nodes.length; i++) {
nodes[i] = new Node();
}
for (int i = 0; i < nodes.length - 1; i++) {
nodes[i].next = nodes[i + 1];
}
Node first = nodes[0];
Node max = nodes[nodes.length - 1];
max.next = null;
assert !hasCycle(first);
assertSameOrder(nodes);
max.next = first;
assert hasCycle(first);
assertSameOrder(nodes);
max.next = max;
assert hasCycle(first);
assertSameOrder(nodes);
max.next = nodes[50];
assert hasCycle(first);
assertSameOrder(nodes);
}답변
Pollard의 rho 알고리즘 살펴보기 . 그것은 똑같은 문제는 아니지만 논리를 이해하고 링크 된 목록에 적용 할 수 있습니다.
(게으 르면 사이클 감지를 확인할 수 있습니다. 확인하십시오. 거북과 토끼에 대한 부분을 확인하십시오.)
여기에는 선형 시간과 2 개의 추가 포인터 만 필요합니다.
자바에서 :
boolean hasLoop( Node first ) {
if ( first == null ) return false;
Node turtle = first;
Node hare = first;
while ( hare.next != null && hare.next.next != null ) {
turtle = turtle.next;
hare = hare.next.next;
if ( turtle == hare ) return true;
}
return false;
}(대부분의 솔루션은 null next과 next.nextnull 을 모두 확인하지 않습니다 . 또한 거북이가 항상 뒤에 있기 때문에 null을 확인하지 않아도됩니다. 토끼는 이미 그렇게했습니다.)
답변
사용자 unicornaddict 는 위의 멋진 알고리즘을 가지고 있지만 불행히도 홀수 길이> = 3의 비 루프 목록에 대한 버그가 포함되어 있습니다. 문제는 fast목록이 끝나기 직전에 “고착”될 수 있다는 것 입니다.slow 것입니다. 루프가 잘못 감지되었습니다.
올바른 알고리즘은 다음과 같습니다.
static boolean hasLoop(Node first) {
if(first == null) // list does not exist..so no loop either.
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list.
while(true) {
slow = slow.next; // 1 hop.
if(fast.next == null)
fast = null;
else
fast = fast.next.next; // 2 hops.
if(fast == null) // if fast hits null..no loop.
return false;
if(slow == fast) // if the two ever meet...we must have a loop.
return true;
}
}답변
이러한 맥락에서, 텍스트 자료는 어디에나 존재합니다. 개념을 이해하는 데 실제로 도움이되는 다이어그램 표현을 게시하고 싶었습니다.
지점 p에서 빠르고 느리게 만나면
빠른 이동 거리 = a + b + c + b = a + 2b + c
느리게 이동 한 거리 = a + b
빠름이 느림보다 2 배 빠르기 때문입니다. 따라서 a + 2b + c = 2 (a + b) 이면 a = c가 됩니다.
따라서 다른 느린 포인터가 head에서 q로 다시 실행될 때 빠른 포인터가 p에서 q로 실행 되므로 포인트 q에서 함께 만나게 됩니다.
public ListNode detectCycle(ListNode head) {
if(head == null || head.next==null)
return null;
ListNode slow = head;
ListNode fast = head;
while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
/*
if the 2 pointers meet, then the
dist from the meeting pt to start of loop
equals
dist from head to start of loop
*/
if (fast == slow){ //loop found
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
return null;
}