用於尋找鍊錶中循環長度的 JavaScript 程式

在這個程式中，我們將得到一個可能包含循環的鍊錶，我們必須找出循環是否存在，然後循環的大小是多少。讓我們使用一個非常著名的方法來借助程式碼來尋找循環的長度，並討論其時間和空間複雜度。

問題簡介

在這個問題中，正如我們上面所看到的，我們給出了一個鍊錶，其中可能包含也可能不包含循環，如果循環存在，我們必須找到循環的長度，否則我們必須返回零，因為有不存在循環。我們將使用 Floyd 循環方法來尋找循環，然後檢查其大小。例如，如果我們給一個鍊錶 -

List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

從包含 8 的節點到包含 4 的節點存在一個循環，這意味著 8 與 4 連接，形成一個長度為 5 的循環，我們必須偵測它。

方法

在本題中，我們將使用Floyd循環方法來偵測循環，然後我們將使用長度查找的概念來尋找循環的長度。讓我們先看看問題的基本步驟，然後我們將轉向佛洛伊德方法和長度方法。

• 首先，我們將建立一個類別來提供鍊錶節點的基本結構，並在其中定義建構函式來初始化節點值。

• 然後我們建立了一個函數來將元素推送到給定的鍊錶。

• 我們使用上面的方法建立了一個鍊錶，然後將最後一個節點連結到另一個節點以在其中形成一個循環。

佛洛伊德演算法

在這個演算法中，我們遍歷鍊錶，一旦進入鍊錶，就無法從任何節點出去。這意味著，如果我們在鍊錶循環部分有兩個指針，其中一個指針一次移動一個節點，另一個指針一次移動兩個節點，它們將在某一點相遇。

• 實作演算法後，我們將呼叫該函數並檢查循環是否存在

• 如果存在循環，我們將呼叫 anther 函數來尋找循環的長度。

• 另一方面，我們將返回並列印不存在循環。

範例

在下面的範例中，我們定義一個鍊錶並向其中新增 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)。

以上是用於尋找鍊錶中循環長度的 JavaScript 程式的詳細內容。更多資訊請關注PHP中文網其他相關文章！