연결된 목록주기

난이도 쉽게
자주 묻는 질문 수행자 아마존 MAQ 삼성
연결된 목록 두 포인터조회수 32

문제 정책

"연결된 목록주기"문제는 연결 목록이 제공된다는 것을 나타냅니다. 루프가 있는지 여부를 찾으십니까?

연결된 목록주기

 주기가있는 연결 목록

1->2->3
No Loop

설명 : 연결 목록 루프가 없다면 같은 노드를 가리키는 두 개의 des가 없었을 것입니다. 또는 다음 노드로 Null을 갖는 노드가 없었을 것입니다.

1->2->3->4
   ^     |
   |_____|
Yes there exists a loop

설명 : 예, 값이 1 인 노드와 값이 4 인 노드가 동일한 노드 2를 가리 키기 때문에 루프가 있습니다.

해싱 방법 사용

암호알고리즘

1. Initialize a hash table of type Node.
2. Start traversing the list. While node of the list is not null check if the current value is already stored in the hash table, if yes return true.
3. Else store it in the hash table and increment the pointer of the hash table.
4. Return false.

해시 테이블을 사용하거나 해시셋 연결 목록에 루프가 있는지 확인합니다. 배열에 중복 항목이 있는지 찾아야 할 때 동일한 기술이 사용됩니다. 반복해서는 안되는 값을 저장하기 위해 HashSet을 사용합니다. HashSet은 모든 요소의 단일 인스턴스 만 저장할 수 있기 때문입니다 (즉, 중복 저장을 허용하지 않음). 이 기능은 우리의 사용 사례에 적합합니다. 따라서 HashSet을 사용하여 동일한 노드를 두 번 찾은 경우 연결 목록을 순회하는 동안 확인합니다. 연결 목록에 루프가 있다는 것을 알고 있습니다. 그러나 동일한 노드를 두 번 찾지 않고 연결 목록을 순회 할 수 있다면. 우리는 어떤 요소도 반복되지 않았고 연결된 목록에 루프가 없다는 것을 알고 있습니다.

암호

연결된 목록주기를 찾는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
struct Node{ 
    int data; 
    struct Node* next; 
}; 
  
void push(struct Node** head_ref, int new_data){ 
    struct Node* new_node = new Node; 
  
    new_node->data = new_data; 
  
    new_node->next = (*head_ref); 
  
    (*head_ref) = new_node; 
} 
  
bool detectCycle(struct Node* h){ 
    unordered_set<Node*> s; 
    while (h != NULL) { 
        if (s.find(h) != s.end()) 
            return true; 
  
        s.insert(h); 
  
        h = h->next; 
    } 
  
    return false; 
} 
  
int main(){ 
    struct Node* head = NULL; 
  
    push(&head, 20); 
    push(&head, 4); 
    push(&head, 15); 
    push(&head, 10); 
  
    head->next->next->next->next = head; 
  
    if(detectCycle(head)) 
        cout << "Loop found"; 
    else
        cout << "No Loop"; 
  
    return 0; 
}
Loop found

링크 된 목록주기를 찾는 Java 프로그램

import java.util.*;
  
class Cycle{ 
  
    static Node head;
    static class Node { 
        int data; 
        Node next; 
        Node(int d) 
        { 
            data = d; 
            next = null; 
        } 
    } 
  
    static public void push(int new_data){ 
        Node new_node = new Node(new_data); 
  
        new_node.next = head; 
  
        head = new_node; 
    } 
  
    static boolean detectCycle(Node h){ 
        HashSet<Node> s = new HashSet<Node>(); 
        while(h != null){ 
            if(s.contains(h)) 
                return true; 
  
            s.add(h); 
  
            h = h.next; 
        } 
  
        return false; 
    } 
  
    public static void main(String[] args){ 
        Cycle list = new Cycle(); 
  
        list.push(20); 
        list.push(4); 
        list.push(15); 
        list.push(10); 
  
        list.head.next.next.next.next = list.head; 
  
        if(detectCycle(head)) 
            System.out.println("Loop found"); 
        else
            System.out.println("No Loop"); 
    } 
}
Loop found

복잡성 분석

시간 복잡성

의 위에) 여기서 n은 주어진 목록에 삽입 된 노드의 수입니다. 우리는 선형 시간 복잡도를 달성 할 수 있도록 O (1)에서 삽입 및 검색을 보장하는 HashSet 또는 unorder_set을 사용했기 때문에.

공간 복잡성

의 위에) 최악의 경우 N 개의 노드를 삽입해야하는 HashSet을 사용했기 때문입니다.

플로이드의주기 찾기 알고리즘

단계

  1. 두 개의 포인터를 느리고 빠르게 사용하십시오.
  2. 느린 포인터를 한 노드 씩 이동하고 각 단계에서 1로 빠르게 이동합니다.
  3. 두 포인터가 어느 지점에서나 만나면 사이클이있는 것입니다.

암호알고리즘

1. Initialize two pointers fast and slow as head of the list.
2. Traverse while fast or slow is not null. Increment slow by 1 node and fast by 2 nodes.
3. Check at each traversal if slow equals to fast, print "Loop found" and return 1.
4. Else return 0 and print "No loop".

암호

연결된 목록주기를 찾는 C ++ 프로그램

#include <bits/stdc++.h> 
using namespace std; 
  
class Node{ 
public: 
    int data; 
    Node* next; 
}; 
  
void push(Node** head_ref, int new_data){ 
    Node* new_node = new Node(); 
  
    new_node->data = new_data; 
  
    new_node->next = (*head_ref); 
  
    (*head_ref) = new_node; 
} 
  
int detectCycle(Node* list){ 
    Node *slow = list, *fast = list; 
  
    while (slow && fast && fast->next) { 
        slow = slow->next; 
        fast = fast->next->next; 
        if (slow == fast) { 
            cout << "Found Loop"; 
            return 1; 
        } 
    } 
    return 0; 
} 
  
int main(){ 
    Node* head = NULL; 
  
    push(&head, 20); 
    push(&head, 4); 
    push(&head, 15); 
    push(&head, 10); 
  
    head->next->next->next->next = head; 
    if(!detectCycle(head))
        cout<<"No Loop"; 
  
    return 0; 
} 
Loop found

링크 된 목록주기를 찾는 Java 프로그램

class Cycle{ 
  
    Node head; 
  
    class Node { 
        int data; 
        Node next; 
        Node(int d) 
        { 
            data = d; 
            next = null; 
        } 
    } 
  
    public void push(int new_data){ 
        Node new_node = new Node(new_data); 
  
        new_node.next = head; 
  
        head = new_node; 
    } 
  
    int detectCycle(){ 
        Node slow = head, fast = head; 
        while (slow != null && fast != null && fast.next != null) { 
            slow = slow.next; 
            fast = fast.next.next; 
            if (slow == fast) { 
                System.out.println("Found loop"); 
                return 1; 
            } 
        } 
        return 0; 
    } 
  
    public static void main(String args[]){ 
        Cycle list = new Cycle(); 
  
        list.push(20); 
        list.push(4); 
        list.push(15); 
        list.push(10); 
  
        list.head.next.next.next.next = list.head; 
  
        if(list.detectCycle()==0)
             System.out.println("No loop");  
    }  
}
Loop found

복잡성 분석

시간 복잡성

의 위에) 여기서 N은 주어진 목록에 삽입 된 노드의 수입니다.

공간 복잡성

O (1) 일정한 추가 공간을 사용했기 때문입니다. 여기에서는 각 노드에 대한 추가 정보를 저장하지 않았습니다. 따라서 우리는 일정한 공간 복잡성을 가지고 있습니다.

연결 목록 데이터 구조를 수정하지 않고 방문한 노드 표시

연결 목록주기를 감지하는 알고리즘

1. Initialize an extra node.
2. Traverse through the list while the head is not null. If head->next is null i.e. there is no cycle, return false.
3. Else if head->next is equal to the extra node, return true.
4. Create a node to store the pointer of the next node.
5. Store extra node in a pointer to the next node.
6. Update the head to the next node.
7. Return false.

여기에서 임시 노드를 만들고 모든 노드를이 새 노드로 가리 킵니다. 따라서 한 번에 이미 임시 노드를 가리키는 노드를 발견하면. 그런 다음 연결 목록에 순환이 포함되지 않는 루프가 있다는 것을 압니다.

암호

연결된 목록주기를 찾는 C ++ 프로그램

#include <iostream> 
using namespace std; 
  
struct Node{ 
    int key; 
    struct Node* next; 
}; 
  
Node* newNode(int key){ 
    Node* temp = new Node; 
    temp->key = key; 
    temp->next = NULL; 
    return temp; 
} 
  
bool detectCycle(Node* head){ 
  
    Node* temp = new Node; 
    while (head != NULL) { 
  
        if(head->next == NULL){ 
            return false; 
        } 
  
        if(head->next == temp){ 
            return true; 
        } 
  
        Node* nex = head->next; 
  
        head->next = temp; 
  
        head = nex; 
    } 
  
    return false; 
} 
  
int main(){ 
    Node* head = newNode(1); 
    head->next = newNode(2); 
    head->next->next = newNode(3); 
    head->next->next->next = newNode(4); 
    head->next->next->next->next = newNode(5); 
  
    head->next->next->next->next->next = head->next->next; 
  
    bool found = detectCycle(head); 
    if(found) 
        cout << "Loop Found"; 
    else
        cout << "No Loop"; 
  
    return 0; 
}
Loop found

링크 된 목록주기를 찾는 Java 프로그램

class Cycle{ 
  
    static class Node { 
        int key; 
        Node next; 
    }; 
  
    static Node newNode(int key){ 
        Node temp = new Node(); 
        temp.key = key; 
        temp.next = null; 
        return temp; 
    } 
  
    static void printList(Node head){ 
        while (head != null) { 
            System.out.print(head.key + " "); 
            head = head.next; 
        } 
        System.out.println(); 
    } 
  
    static boolean detectCycle(Node head){ 
  
        Node temp = new Node(); 
        while (head != null) { 
  
            if(head.next == null){ 
                return false; 
            } 
  
            if (head.next == temp) { 
                return true; 
            } 
  
            Node nex = head.next; 
  
            head.next = temp; 
  
            head = nex; 
        } 
  
        return false; 
    } 
  
    public static void main(String args[]){ 
        
        Node head = newNode(1); 
        head.next = newNode(2); 
        head.next.next = newNode(3); 
        head.next.next.next = newNode(4); 
        head.next.next.next.next = newNode(5); 
  
        head.next.next.next.next.next = head.next.next; 
  
        boolean found = detectCycle(head); 
        if (found) 
            System.out.println("Loop Found"); 
        else
            System.out.println("No Loop"); 
    } 
}
Loop found

복잡성 분석

시간 복잡성

의 위에) 여기서 N은 주어진 목록에 삽입 된 노드의 수입니다.

공간 복잡성

O (1) 일정한 추가 공간을 사용했기 때문입니다. 여기서 우리는 다른 모든 노드가 가리키는 단일 새 노드를 만들었습니다.

Translate »