Байланышкан тизме цикли  


Кыйынчылык деңгээли жеңил
Көп суралган Accolite Amazon MAQ Samsung
Байланышкан тизме Эки көрсөткүч

Маселени билдирүү  

"Байланышкан тизмектин цикли" көйгөйүндө сизге байланышкан тизме берилгендиги айтылат. Анын ичинде кандайдыр бир цикл бар же жок экендигин тапкыла?

Байланышкан тизме циклитөөнөч

 Цикл менен байланышкан тизме

мисал  

1->2->3
No Loop

Түшүндүрмө: байланышкан тизме эч кандай циклди камтыбайт, анткени эгерде андай болсо, анда бир эле түйүнгө багытталган эки иш жок болмок. Же болбосо Null кийинки түйүн болгон бир дагы түйүн болмок эмес.

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

Түшүндүрмө: Ооба, цикл бар, анткени 1 мааниси бар түйүн жана 4 мааниси бар түйүн ошол эле 2 түйүнүн көрсөтүп турат.

Хэштөө ыкмасын колдонуу  

Algorithm

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 ар кандай элементтердин бир гана нускасын сактоого мүмкүндүк берет (б.а. ал копияларды сактоого мүмкүнчүлүк бербейт). Бул функция биздин колдонууга ылайыктуу. Ошентип, биз бир түйүндү эки жолу тапсак, байланышкан тизмеден өтүп жатканда 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

Комплекстик анализ

Убакыт татаалдыгы

O (N) бул жерде n - берилген тизмедеги киргизилген түйүндөрдүн саны. HashSet же unordered_set колдонуп, O (1) киргизүүнү жана издөөнү камсыз кылат, бул убакыттын сызыктуу татаалдыгына жетишүүгө мүмкүндүк берди.

Космостун татаалдыгы

O (N) анткени биз HashSetти колдонуп, анда эң начар учурга N түйүндөрүн киргизишибиз керек.

Флойддун цикл табуу алгоритми  

кадамдар

  1. Эки көрсөткүчтү жай жана тез колдонуңуз.
  2. Жай көрсөткүчтү 1 түйүнгө жылдырып, ар бир кадам сайын 2 ылдамдыкта.
  3. Эгерде эки көрсөткүч каалаган учурда жолугушса, анда цикл бар.
ошондой эле
Суу сактагычтан үлгү алуу

Algorithm

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

Комплекстик анализ

Убакыт татаалдыгы

O (N) бул жерде 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.

Бул жерде убактылуу түйүн түздүк, бардык түйүндөрдү ушул жаңы түйүнгө багыттайбыз. Ошентип, эгерде биз бир эле учурда убактылуу түйүндү көрсөткөн түйүнгө туш келсек. Ошондо шилтеме тизмесинде цикл камтылбаган цикл бар экендигин билебиз.

ошондой эле
1d массивинин Leetcode чечиминин суммасы

коду

Байланышкан тизме циклин табуу үчүн 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

Комплекстик анализ

Убакыт татаалдыгы

O (N) бул жерде N - берилген тизмедеги киргизилген түйүндөрдүн саны.

Космостун татаалдыгы

O (1) анткени биз туруктуу кошумча мейкиндикти колдондук. Бул жерде биз башка түйүндөр көрсөткөн жаңы гана түйүндү жараттык.