Bağlı siyahı dövrü

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit Amazon MAQ Samsung
Bağlı siyahı İki işarəBaxılıb 32

Problem bəyanat

"Bağlı siyahı dövrü" problemi sizə əlaqəli siyahı verildiyini bildirir. Hər hansı bir döngə olub olmadığını tapın?

Bağlı siyahı dövrüPin

 Siyahı dövrü ilə əlaqələndirilir

misal

1->2->3
No Loop

İzahat: The əlaqəli siyahı heç bir döngə ehtiva etmir, çünki əgər belə olsaydı, eyni düyünə işarə edən iki iş olmazdı. Və ya Null-un növbəti node olduğu hər hansı bir düyün olmazdı.

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

İzahat: Bəli, bir döngə var, çünki dəyəri 1 olan qovşaq və dəyəri 4 olan qovşaq eyni qovşağı 2 göstərir.

Hashing metodundan istifadə

Alqoritm

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.

Burada bir hash masa və ya istifadə edirik HashSet əlaqəli siyahıda bir döngünün olub olmadığını tapmaq. Dizimizdə dublikat olub olmadığını tapmaq lazım olduqda eyni texnika istifadə olunur. Təkrarlanmamalı olduğumuz dəyəri saxlamaq üçün HashSet istifadə edirik. Çünki HashSet hər hansı bir elementin yalnız bir nümunəsini saxlamağa imkan verir (yəni təkrarlamaları saxlamağa icazə vermir). Bu funksionallıq istifadə vəziyyətimizə uyğundur. Beləliklə, eyni düyünü iki dəfə tapdığımızı, əlaqəli siyahıdan keçərkən yoxlamaq üçün HashSet istifadə edirik. əlaqəli siyahıda bir döngü olduğunu bilirik. Ancaq eyni düyünü iki dəfə tapmadan əlaqəli siyahıdan keçə bilsək. elementlərin heç birinin təkrarlanmadığını və əlaqəli siyahıda bir döngənin olmadığını bilirik.

Kodu

Bağlı siyahı dövrü tapmaq üçün C ++ Proqramı

#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

Bağlı siyahı dövrü tapmaq üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N) burada n - verilmiş siyahıya daxil edilmiş qovşaqların sayı. HashSet və ya unordered_set istifadə etdiyimizdən O (1) -ə daxil olmağı və axtarış etməyi təmin edir ki, bu da xətti zaman mürəkkəbliyinə nail olmağa imkan verir.

Kosmik Mürəkkəblik

O (N) çünki ən pis vəziyyətdə N qovşaqları əlavə etməli olduğumuz bir HashSet istifadə etdik.

Floyd-un dövrü tapmaq alqoritmi

Addımlar

  1. Yavaş və sürətli iki göstəricidən istifadə edin.
  2. Yavaş göstəricini 1 düyünlə və hər addımda 2-də sürətlə hərəkət edin.
  3. Hər iki göstərici istənilən nöqtədə görüşürsə, dövr mövcuddur.

Alqoritm

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".

Kodu

Bağlı siyahı dövrü tapmaq üçün C ++ Proqramı

#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

Bağlı siyahı dövrü tapmaq üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N) burada N - verilmiş siyahıya daxil edilmiş qovşaqların sayı.

Kosmik Mürəkkəblik

O (1) çünki daimi əlavə yerdən istifadə edirdik. burada qovşaqların hər biri ilə bağlı əlavə məlumat saxlamamışıq. Beləliklə, daimi kosmik mürəkkəbliyə sahibik.

Bağlı siyahı məlumat strukturunu dəyişdirmədən ziyarət edilmiş qovşaqların işarələnməsi

Bağlı siyahı dövrü aşkar etmək üçün alqoritm

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.

Burada müvəqqəti bir düyün yaratdıq, bütün qovşaqları bu yeni düyünə yönəldirik. Beləliklə, bir anda müvəqqəti düyünü göstərən bir düyünə rast gəlsək. Sonra bilirik ki, əlaqəli siyahıda dövrü olmayan başqa bir döngə var.

Kodu

Bağlı siyahı dövrü tapmaq üçün C ++ Proqramı

#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

Bağlı siyahı dövrü tapmaq üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N) burada N - verilmiş siyahıya daxil edilmiş qovşaqların sayı.

Kosmik Mürəkkəblik

O (1) çünki daimi əlavə yerdən istifadə edirdik. Burada bütün digər qovşaqların işarə etdiyi tək bir yeni qovşaq yaratdıq.

Translate »