資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究JavaScript 查詢迴圈連結串列長度的程式
在本程式中，我們將得到一個可能包含迴圈的連結串列，我們必須找到如果存在迴圈，那麼迴圈的大小是多少。讓我們用程式碼來介紹一種非常著名的查詢迴圈長度的方法，並討論其時間和空間複雜度。
問題介紹
在這個問題中，如上所述，我們得到一個可能包含或不包含迴圈的連結串列，如果存在迴圈，我們必須找到迴圈的長度，否則我們必須返回零，因為不存在迴圈。我們將使用 Floyd 迴圈方法來查詢迴圈，然後檢查其大小。例如，如果我們得到一個如下所示的連結串列：
List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
並且從包含 8 的節點到包含 4 的節點存在一個迴圈，這意味著 8 連線到 4，形成長度為 5 的迴圈，我們必須檢測到它。
方法
在這個問題中，我們將使用 Floyd 迴圈方法來檢測迴圈，然後我們將使用長度查詢的概念來查詢迴圈的長度。讓我們首先了解問題的基本步驟，然後我們將轉向 Floyd 方法和長度方法。
首先，我們將建立類以提供連結串列節點的基本結構，並在其中定義建構函式以初始化節點值。
然後，我們建立了一個函式來將元素推入給定的連結串列。
我們使用上述方法建立了一個連結串列，然後我們將最後一個節點連結到另一個節點，以在其內部建立一個迴圈。
Floyd 演算法
在這個演算法中，我們遍歷連結串列，一旦我們進入連結串列迴圈部分，我們就無法從任何節點離開。這意味著如果我們在該連結串列迴圈部分有兩個指標，一個指標每次向前移動一個節點，另一個指標每次向前移動兩個節點，它們將在某個點相遇。
在實現演算法之後，我們將呼叫該函式並檢查迴圈是否存在。
如果迴圈存在，我們將呼叫另一個函式來查詢迴圈的長度。
否則，我們將返回並列印不存在迴圈。
示例
在下面的示例中，我們定義了一個連結串列並向其中添加了 8 個節點。我們透過將節點 8 連線到節點 4 來在連結串列中建立一個迴圈。因此，它形成了一個包含五個節點的迴圈。
// class to provide the structure to the linked list node
class Node{
constructor(data) {
this.value = data
this.next = null;
}
}
// function to add values in a linked list
function push(data, head) {
var new_node = new Node(data);
if(head == null) {
head = new_node;
return head;
}
var temp = head
while(temp.next != null) {
temp = temp.next;
}
temp.next = new_node;
return head;
}
// function to find the length in the loop
function length(loop_node) {
var count = 1;
var temp = loop_node;
while(temp.next != loop_node) {
count++;
temp = temp.next;
}
console.log("The length of the loop in the given linked list is: " + count);
}
// function to find the cycle in the given list
// if the cycle is found then call the length function
function find_node(head) {
var slow_ptr = head;
var fast_ptr = head;
while(slow_ptr != null && fast_ptr != null && fast_ptr.next != null) {
slow_ptr = slow_ptr.next;
fast_ptr = fast_ptr.next.next;
if(slow_ptr == fast_ptr) {
length(slow_ptr);
return;
}
}
console.log("There is no loop present in the given linked list");
}
var head = null;
head = push(1,head)
head = push(2,head)
head = push(3,head)
head = push(4,head)
head = push(5,head)
head = push(6,head)
head = push(7,head)
head = push(8,head)
// making loop in a linked list by connecting 8 to four
var temp = head;
while(temp.value != 4){
temp = temp.next;
}
var temp2 = head;
while(temp2.next != null){
temp2 = temp2.next
}
temp2.next = temp
// finding the length of the loop
find_node(head)
時間和空間複雜度
在上面的程式碼中，我們只遍歷了整個連結串列一次，對於迴圈部分最多遍歷三次，這使得時間複雜度為線性。因此，上述程式碼的時間複雜度為線性，即 O(N)，其中 N 是連結串列的大小。
由於我們沒有使用任何額外的空間，因此程式的空間複雜度為 O(1)。
結論
在本教程中，我們學習瞭如何透過在 JavaScript 語言中實現概念來查詢連結串列中存在的迴圈的長度。我們使用了 Floyd 的迴圈查詢演算法來查詢給定連結串列中的迴圈，然後我們只使用 while 迴圈遍歷迴圈並查詢其長度。上述程式碼的時間複雜度為 O(N)，空間複雜度為 O(1)。
122 次檢視
