링크 리스트에서 루프를 검출하려면 어떻게 해야 합니다.

링크 리스트에서 루프를 검출하려면 어떻게 해야 합니다.

Java에서 링크된 목록 구조를 가지고 있다고 가정해 보십시오.노드:

class Node {
    Node next;
    // some user data
}

각 노드는 다음 노드를 가리키지만 마지막 노드는 다음 노드가 null입니다.목록에 루프가 포함되어 있을 가능성이 있다고 가정합니다.즉, 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;
    }
}

홀수 길이의 리스트를 올바르게 처리해, 선명도를 향상시키는 고속/저속 솔루션의 개량점을 다음에 나타냅니다.

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
}

Floyd 알고리즘보다 우수합니다.

Richard Brent는 대체 사이클 검출 알고리즘을 설명했습니다.이것은 토끼와 거북이의 사이클과 거의 비슷하지만, 여기서 느린 노드는 움직이지 않고 나중에 일정한 간격으로 고속 노드의 위치로 "이동 보고"됩니다.

설명은 브렌트 사이클 검출 알고리즘(The Teleporting Turtle)에서 확인할 수 있습니다.Brent는 자신의 알고리즘이 Floyd의 사이클 알고리즘보다 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);
}

거북이와 토끼

폴라드의 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;
}

(에서는, 양쪽 next ★★★★★★★★★★★★★★★★★」next.next를 참조해 주세요.또한 거북이는 항상 뒤에 있기 때문에 토끼가 이미 그렇게 했기 때문에 늘을 확인할 필요는 없습니다.)

이런 맥락에서, 텍스트 자료들은 도처에 널려 있다.개념 파악에 도움이 되는 도식 표현을 게재하고 싶었습니다.

빠른 것과 느린 것이 p 지점에서 만나면

고속 = a+b+c+b = a+2b+c로 이동한 거리

저속 주행 거리 = a+b

왜냐하면 속도가 느린 속도보다 2배 빠르기 때문이다.a+2b+c = 2(a+b)이면 a=c가 됩니다.

따라서 다른 저속 포인터가 헤드에서 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;
}

사용자 uniconaddict에는 위의 알고리즘이 있지만 안타깝게도 홀수 길이 > = 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;
    }
}

알고리즘.

public static boolean hasCycle (LinkedList<Node> list)
{
    HashSet<Node> visited = new HashSet<Node>();

    for (Node n : list)
    {
        visited.add(n);

        if (visited.contains(n.next))
        {
            return true;
        }
    }

    return false;
}

복잡성

Time ~ O(n)
Space ~ O(n)

다음은 최선의 방법이 아닐 수 있습니다. O(n^2)입니다.하지만, 그것은 (결국) 그 일을 완수하는 데 도움이 될 것이다.

count_of_elements_so_far = 0;
for (each element in linked list)
{
    search for current element in first <count_of_elements_so_far>
    if found, then you have a loop
    else,count_of_elements_so_far++;
}

public boolean hasLoop(Node start){   
   TreeSet<Node> set = new TreeSet<Node>();
   Node lookingAt = start;

   while (lookingAt.peek() != null){
       lookingAt = lookingAt.next;

       if (set.contains(lookingAt){
           return false;
        } else {
        set.put(lookingAt);
        }

        return true;
}   
// Inside our Node class:        
public Node peek(){
   return this.next;
}

(저는 아직 자바와 프로그래밍에 익숙하지 않습니다) 제 무지를 용서해 주세요.근데 왜 위의 것은 안 먹힐까요?

이게 계속 공간 문제를 해결하진 못하는 것 같은데...적어도 적당한 시간 안에 도착하죠, 그렇죠?링크 리스트의 공간과 n개의 요소가 있는 집합의 공간(n은 링크 리스트 내의 요소 수 또는 루프가 될 때까지의 요소 수)만 사용합니다.그리고 당분간은 최악의 경우 분석을 통해 O(nlog(n)를 제안할 수 있습니다.Contains()의 SortedSet 검색은 log(n)(javadoc을 확인하지만 TreeSet의 기본 구조는 TreeMap이며, TreeMap은 빨간색-검은색 트리로 되어 있습니다.최악의 경우(루프가 없는 경우 또는 루프가 없는 경우)에는 n-lookup을 실행해야 합니다.

할 수 Node이치노 hasLoop()는 OO(n)의 합니다.counter것이 적적 ?결 결? ?? ??? ''를 않고 할 수 있는 요?Node (에서는 (실제 구현에서는) 더 방법이 RemoveNode(Node n)의 개요)

public class LinkedNodeList {
    Node first;
    Int count;

    LinkedNodeList(){
        first = null;
        count = 0;
    }

    LinkedNodeList(Node n){
        if (n.next != null){
            throw new error("must start with single node!");
        } else {
            first = n;
            count = 1;
        }
    }

    public void addNode(Node n){
        Node lookingAt = first;

        while(lookingAt.next != null){
            lookingAt = lookingAt.next;
        }

        lookingAt.next = n;
        count++;
    }

    public boolean hasLoop(){

        int counter = 0;
        Node lookingAt = first;

        while(lookingAt.next != null){
            counter++;
            if (count < counter){
                return false;
            } else {
               lookingAt = lookingAt.next;
            }
        }

        return true;

    }



    private class Node{
        Node next;
        ....
    }

}

일정한 O(1)시간 내에 실행할 수도 있습니다(단, 매우 빠르거나 효율적이지는 않습니다).N개의 레코드에 의하면, 컴퓨터의 메모리에 격납할 수 있는 노드의 수는 한정되어 있습니다.N개 이상의 레코드를 통과하면 루프가 발생합니다.

여기 실행 가능한 코드가 있습니다.

가 한 노드 복잡도)를입니다.O(1)링크를 추적합니다.

여기서 흥미로운 사실은 링크된 목록에서 사이클을 검출하는 데 도움이 된다는 것입니다.이 작업을 진행하면 시작점(루트 노드)으로 돌아갈 것으로 예상되지 않으며 임시 노드 중 하나가 루트 노드를 가리키는 사이클이 없는 한 null로 이동해야 하기 때문입니다.

는 " " 입니다.O(n)의 복잡성은 '공간의 복잡성'입니다.O(1).

링크된 목록의 클래스 노드를 다음에 나타냅니다.

public class LinkedNode{
    public LinkedNode next;
}

다음은 마지막 노드가 두 번째 노드를 가리키는 3개 노드의 간단한 테스트 케이스의 주요 코드입니다.

    public static boolean checkLoopInLinkedList(LinkedNode root){

        if (root == null || root.next == null) return false;

        LinkedNode current1 = root, current2 = root.next, current3 = root.next.next;
        root.next = null;
        current2.next = current1;

        while(current3 != null){
            if(current3 == root) return true;

            current1 = current2;
            current2 = current3;
            current3 = current3.next;

            current2.next = current1;
        }
        return false;
    }

다음은 마지막 노드가 두 번째 노드를 가리키는 3개 노드의 간단한 테스트 사례입니다.

public class questions{
    public static void main(String [] args){

        LinkedNode n1 = new LinkedNode();
        LinkedNode n2 = new LinkedNode();
        LinkedNode n3 = new LinkedNode();
        n1.next = n2;
        n2.next = n3;
        n3.next = n2;

        System.out.print(checkLoopInLinkedList(n1));
    }
}

 // To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
    Node slower, faster;
    slower = head;
    faster = head.next; // start faster one node ahead
    while (true) {

        // if the faster pointer encounters a NULL element
        if (faster == null || faster.next == null)
            return false;
        // if faster pointer ever equals slower or faster's next
        // pointer is ever equal to slower then it's a circular list
        else if (slower == faster || slower == faster.next)
            return true;
        else {
            // advance the pointers
            slower = slower.next;
            faster = faster.next.next;
        }
    }
}

boolean hasCycle(Node head) {

    boolean dec = false;
    Node first = head;
    Node sec = head;
    while(first != null && sec != null)
    {
        first = first.next;
        sec = sec.next.next;
        if(first == sec )
        {
            dec = true;
            break;
        }

    }
        return dec;
}

Java의 linked list에서 루프를 검출하려면 위의 함수를 사용합니다.

링크 리스트의 루프 검출은 가장 간단한 방법 중 하나로 실행할 수 있습니다.그 결과, 해시 맵을 사용하는 O(N) 또는 정렬 베이스의 어프로치를 사용하는 O(NlogN)가 복잡해집니다.

목록을 머리부터 이동하면서 정렬된 주소 목록을 작성합니다.새 주소를 삽입할 때 정렬된 목록에 주소가 이미 있는지 확인합니다. 이 경우 O(logN)의 복잡성이 발생합니다.

일정 시간 또는 공간이 소요되도록 할 수 없습니다. 둘 다 목록 크기에 따라 증가합니다.

IdentityHashMap(IdentityHashSet이 아직 없는 경우)을 사용하여 각 노드를 맵에 저장합니다.노드를 저장하기 전에 containsKey를 호출합니다.노드가 이미 존재하는 경우 주기가 있습니다.

ItentityHashMap은 .dll 대신 ==를 사용하기 때문에 객체의 내용이 동일한지 아닌 메모리 내 위치를 확인할 수 있습니다.

내가 이 일을 처리하기에는 너무 늦고 새로워질지도 몰라.하지만 여전히..

노드의 주소와 가리키는 "다음" 노드를 테이블에 저장할 수 없는 이유는 무엇입니까?

이런 식으로 표를 만들 수 있다면

node present: (present node addr) (next node address)

node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200)
node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300)
node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400)
node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500)
node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600)
node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400)

그래서 사이클이 형성되어 있습니다.

이 접근방식에서는 공간 오버헤드가 발생하지만 구현이 간단합니다.

루프는 Map에 노드를 저장함으로써 식별할 수 있습니다.노드를 배치하기 전에 노드가 이미 존재하는지 확인하십시오.맵에 노드가 이미 존재하는 경우 Linked List에 루프가 있음을 의미합니다.

public boolean loopDetector(Node<E> first) {  
       Node<E> t = first;  
       Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();  
       while (t != null) {  
            if (map.containsKey(t)) {  
                 System.out.println(" duplicate Node is --" + t  
                           + " having value :" + t.data);  

                 return true;  
            } else {  
                 map.put(t, t);  
            }  
            t = t.next;  
       }  
       return false;  
  }  

이 코드는 최적화되어 있어 최적의 답변으로 선택된 코드보다 더 빨리 결과를 얻을 수 있습니다.이 코드를 사용하면 'best answer' 방식을 따를 경우 다음과 같은 경우에 발생할 수 있는 순방향 및 역방향 노드 포인터를 추적하는 매우 긴 프로세스에 들어가는 것을 방지할 수 있습니다.다음 내용을 대충 훑어보면 내가 말하고자 하는 것을 알 수 있을 것이다.그런 다음 아래의 주어진 방법을 통해 문제를 살펴보고 정답을 찾기 위해 수행된 단계 수를 측정하십시오.

1->2->9->3^-------^

코드는 다음과 같습니다.

boolean loop(node *head)
{
 node *back=head;
 node *front=head;

 while(front && front->next)
 {
  front=front->next->next;
  if(back==front)
  return true;
  else
  back=back->next;
 }
return false
}

Java에서의 솔루션

boolean detectLoop(Node head){
    Node fastRunner = head;
    Node slowRunner = head;
    while(fastRunner != null && slowRunner !=null && fastRunner.next != null){
        fastRunner = fastRunner.next.next;
        slowRunner = slowRunner.next;
        if(fastRunner == slowRunner){
            return true;
        }
    }
    return false;
}

위의 답변에서 제시한 Floyd의 거북이 알고리즘을 사용할 수도 있습니다.

이 알고리즘은 단일 링크 목록에 닫힌 사이클이 있는지 여부를 확인할 수 있습니다.이는 서로 다른 속도로 이동하는 두 포인터로 목록을 반복함으로써 달성할 수 있습니다.이와 같이, 사이클이 있는 경우, 두 포인터는 장래의 어느 시점에서 만나게 됩니다.

상기 알고리즘을 자바 언어로 구현한 코드 스니펫을 첨부한 링크드 리스트 데이터 구조에 관한 블로그 투고를 확인하시기 바랍니다.

안부 전해요,

Andreas(@xnorcode)

여기 사이클을 검출하기 위한 솔루션이 있습니다.

public boolean hasCycle(ListNode head) {
            ListNode slow =head;
            ListNode fast =head;

            while(fast!=null && fast.next!=null){
                slow = slow.next; // slow pointer only one hop
                fast = fast.next.next; // fast pointer two hops 

                if(slow == fast)    return true; // retrun true if fast meet slow pointer
            }

            return false; // return false if fast pointer stop at end 
        }

// 링크 목록 찾기 루프 함수

int findLoop(struct Node* head)
{
    struct Node* slow = head, *fast = head;
    while(slow && fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return 1;
    }
 return 0;
}

링크된 목록 구조가 java.util을 구현하는 경우.리스트. 리스트의 크기를 사용해서 리스트에서 우리의 위치를 추적할 수 있어.

현재 위치를 마지막 노드의 위치와 비교하여 노드를 이동할 수 있습니다.만약 우리의 현재 위치가 마지막 위치를 넘으면, 리스트가 어딘가에 루프를 가지고 있는 것을 알 수 있습니다.

이 솔루션에는 일정한 공간이 필요하지만 목록 크기가 커질수록 완료 시간이 선형적으로 늘어납니다.

class LinkedList implements List {
    Node first;
    int listSize;
    
    @Override
    int size() {
        return listSize;
    }

    [..]

    boolean hasLoop() {
        int lastPosition = size();
        int currentPosition = 1;
        Node next = first;
        while(next != null) {
           if (currentPosition > lastPosition) return true;
           next = next.next;
           currentPosition++;
        }
        return false;
    }
}

또는 유틸리티로서:

static boolean hasLoop(int size, Node first) {
    int lastPosition = size;
    int currentPosition = 1;
    Node next = first;
    while(next != null) {
       if (currentPosition > lastPosition) return true;
       next = next.next;
       currentPosition++;
    }
    return false;
}

이 답변이 Java에 적용되는지는 잘 모르겠습니다만, 아직 여기에 속한다고 생각합니다.

최신 아키텍처에 관한 포인터로 작업할 때는 항상 CPU 워드의 정렬을 기대할 수 있습니다.64비트 아키텍처에서는 포인터의 처음 3비트는 항상 제로입니다.이를 통해 이 메모리를 사용하여 이미 본 포인터를 첫 번째 비트에 1을 기록함으로써 마킹할 수 있습니다.

첫 번째 비트에 이미 1이 입력된 포인터를 발견하면 루프가 발견되고 그 후 구조를 다시 통과하여 해당 비트를 마스킹해야 합니다.알았어!

이 접근방식은 포인터태깅이라고 불리며, 예를 들어 Haskell이 일부 최적화에 사용하는 등 저수준 프로그래밍에서 과도하게 사용됩니다.

public boolean isCircular() {

    if (head == null)
        return false;

    Node temp1 = head;
    Node temp2 = head;

    try {
        while (temp2.next != null) {

            temp2 = temp2.next.next.next;
            temp1 = temp1.next;

            if (temp1 == temp2 || temp1 == temp2.next) 
                return true;    

        }
    } catch (NullPointerException ex) {
        return false;

    }

    return false;

}

언급URL : https://stackoverflow.com/questions/2663115/how-to-detect-a-loop-in-a-linked-list