鍊錶順時針旋轉的JavaScript程序

JavaScript 中鍊錶的基本結構可以使用 JavaScript 中的類別創建，然後可以將節點從一個位置移動到另一個位置以進行旋轉。在本文中，我們將學習如何在 JavaScript 程式語言中順時針旋轉鍊錶。我們將看到用於深入理解這些概念的程式碼。

在給定的問題中，我們給了一個鍊錶，我們必須以順時針方式旋轉它。這意味著，我們必須在每次移動中將最後一個元素放在第一位，如果我們必須旋轉 k 次，那麼我們必須將最後一個元素放在鍊錶的頭或起始節點之前。要建立我們之前看到的鍊錶，我們需要一個類別將資料和指向下一個元素的指標綁定在一起。

鍊錶結構

範例

首先，我們將建立一個類別節點，用於儲存目前節點的值和指向下一個節點的指標。之後，我們將建立一個推送函數來幫助建立連結列表，最後，我們將建立一個函數顯示來幫助列印連結列表。讓我們先看程式碼 -

// creating the class for the linked list
class Node{
   // defining the constructor for class
   constructor(){
      this.next = null; // pointer to hold the next value 
      this.value = 0; // curent value in the linked list 
   }
}
// defining push function for linked list 
function push(head,data){
   var new_node = new Node();
   new_node.value = data;
   if(head == null){
      return new_node;
   }
   var temp = head;
   while(temp.next != null){
      temp = temp.next;
   }
   temp.next = new_node;
   return head;
}
function display(head){
   var temp = head;
   var values = 0;
   while(temp){   
      values = values + temp.value + " -> ";
      temp = temp.next;
   }
   console.log(values + "null")
}
var head = null;
for(var i = 1;i<6;i++){
   head = push(head,i);
}
display(head)

在上面的程式碼中，我們使用 class 關鍵字建立了一個類，並使用「this」關鍵字建立了一個部分來儲存資料和指向類別建構函式中下一個節點的指標。

之後，我們定義了一個推送函數，該函數將採用兩個參數，第一個參數是鍊錶的頭，第二個參數是我們要新增到鍊錶中的新節點的資料。在函數中，我們建立了新節點並將值儲存在其中。我們檢查頭是否為空（這意味著我們將添加第一個元素），然後我們將簡單地返回新節點，否則使用循環我們將轉到鍊錶的末尾並在那裡添加新節點。

問題的解決方法

建立類別並定義所需的基本函數後，我們將轉到主函數，在該函數中我們將定義將最後 k 個元素移至鍊錶前面的函數，該函數表示鍊錶的旋轉。有兩種方法可以將最後 k 個元素添加到第一個元素，這等於鍊錶的右旋轉，例如 -

我們給了一個鍊錶：1 -> 2 -> 3 -> 4 -> 5 ->null

我們想要以順時針方式旋轉列出的連結一次，那麼它看起來像這樣 -

5 -> 1 -> 2 -> 3 -> 4 -> null

同樣，對於鍊錶的旋轉3次，鍊錶將像這樣 -

Initially Linked list: 1 -> 2 -> 3 -> 4 -> 5 -> null
After the first rotation: 5 -> 1 -> 2 -> 3 -> 4 -> null
After the second rotation: 4 -> 5 -> 1 -> 2 -> 3 -> null
After the third rotation: 3 -> 4 -> 5 -> 1 -> 2 -> null

我們有兩種方法來添加鍊錶前面的最後一個元素，要么一個一個地添加，要么一次全部添加。

逐一旋轉鍊錶

範例

在這種方法中，我們將轉到最後一個節點，然後將其移動到先前的頭節點並更新頭節點。讓我們先看一下程式碼 -

// creating the class for linked list
class Node{
   // defining the constructor for class
   constructor(){
      this.next = null; // pointer to hold the next value 
      this.value = 0; // curent value in the linked list 
   }
}
// defining push function for linked list 
function push(head,data){
   var new_node = new Node();
   new_node.value = data;
   if(head == null){
      return new_node;
   }
   var temp = head;
   while(temp.next != null){
      temp = temp.next;
   }
   temp.next = new_node;
   return head;
}

function display(head){
   var temp = head;
   var values = 0
   while(temp){
      values =  values + temp.value + " -> ";
      temp = temp.next;
   }
   console.log(values + "null")
}
function rotate(head, k){
   while(k--){
      var temp = head;
      while(temp.next.next != null){
         temp = temp.next;
      }
      var new_head = temp.next;
      temp.next = null;
      new_head.next = head;
      head = new_head;
   }
   return head;
}
var head = null;
for(var i = 1;i<6;i++){
   head = push(head,i);
}
head = rotate(head,3);
display(head);

在上面的程式碼中，我們使用了上面定義的基本函數鍊錶的程式碼，只是新增了一個新函數來旋轉鍊錶。

在函數rotate中，我們首先使用while循環遍歷鍊錶k次，並且在每次迭代中，我們都到達鍊錶的倒數第二個元素。然後我們從鍊錶中刪除鍊錶的最後一個元素，並將其放在鍊錶頭部之前的前面。最後，我們返回了新的頭，並使用顯示函數顯示了新的鍊錶。

時間與空間複雜度

我們已經移動了鍊錶 k 次，鍊錶的大小是 N，所以程式的整體時間複雜度是 O(N*K)。另外，我們沒有使用任何額外的空間，因此程式的空間複雜度是 O(1)，這是一個常數。

一次旋轉鍊錶

在前面的程式碼中，我們將元素逐一添加，這花費了 O(N*N) 的時間，以便我們可以更好地移動鍊錶並獲取鍊錶的大小。之後，我們將再次遍歷鍊錶並獲取最後 k 個元素並將它們添加到鍊錶的前面，這將使程式的時間複雜度為 O(1)。

結論

在本教學中，我們學習如何在 JavaScript 程式語言中順時針旋轉鍊錶。我們已經看到了深入理解概念的程式碼。 JavaScript 中鍊錶的基本結構可以使用 JavaScript 中的類別來創建，然後可以將節點從一個位置移動到另一個位置以進行旋轉。程式的時間複雜度為O(N*N)，可以進一步提升到O(N)，而程式的空間複雜度為O(1)。

以上是鍊錶順時針旋轉的JavaScript程序的詳細內容。更多資訊請關注PHP中文網其他相關文章！