JavaScript 中鏈表的基本結(jié)構(gòu)可以使用 JavaScript 中的類創(chuàng)建，然后可以將節(jié)點從一個位置移動到另一個位置以進(jìn)行旋轉(zhuǎn)。在本文中，我們將學(xué)習(xí)如何在 JavaScript 編程語言中順時針旋轉(zhuǎn)鏈表。我們將看到用于深入理解這些概念的代碼。

在給定的問題中，我們給出了一個鏈表，我們必須以順時針方式旋轉(zhuǎn)它。這意味著，我們必須在每次移動中將最后一個元素放在第一位，如果我們必須旋轉(zhuǎn) k 次，那么我們必須將最后一個元素放在鏈表的頭或起始節(jié)點之前。要創(chuàng)建我們之前看到的鏈表，我們需要一個類將數(shù)據(jù)和指向下一個元素的指針綁定在一起。

鏈表結(jié)構(gòu)

示例

首先，我們將創(chuàng)建一個類節(jié)點，用于存儲當(dāng)前節(jié)點的值和指向下一個節(jié)點的指針。之后，我們將創(chuàng)建一個推送函數(shù)來幫助創(chuàng)建鏈接列表，最后，我們將創(chuàng)建一個函數(shù)顯示來幫助打印鏈接列表。讓我們先看代碼 -

// 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 關(guān)鍵字創(chuàng)建了一個類，并使用“this”關(guān)鍵字創(chuàng)建了一個部分來存儲數(shù)據(jù)和指向類構(gòu)造函數(shù)中下一個節(jié)點的指針。

之后，我們定義了一個推送函數(shù)，該函數(shù)將采用兩個參數(shù)，第一個參數(shù)是鏈表的頭，第二個參數(shù)是我們要添加到鏈表中的新節(jié)點的數(shù)據(jù)。在函數(shù)中，我們創(chuàng)建了新節(jié)點并將值存儲在其中。我們檢查頭是否為空（這意味著我們將添加第一個元素），然后我們將簡單地返回新節(jié)點，否則使用循環(huán)我們將轉(zhuǎn)到鏈表的末尾并在那里添加新節(jié)點。

問題的解決方法

創(chuàng)建類并定義所需的基本函數(shù)后，我們將轉(zhuǎn)到主函數(shù)，在該函數(shù)中我們將定義將最后 k 個元素移動到鏈表前面的函數(shù)，該函數(shù)表示鏈表的旋轉(zhuǎn)。有兩種方法可以將最后 k 個元素添加到第一個元素，這等于鏈表的右旋轉(zhuǎn)，例如 -

我們給出了一個鏈表：1 -> 2 -> 3 -> 4 -> 5 ->null

我們想要以順時針方式旋轉(zhuǎn)列出的鏈接一次，那么它看起來像這樣 -

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

同樣，對于鏈表的旋轉(zhuǎn)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

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

逐一旋轉(zhuǎn)鏈表

示例

在這種方法中，我們將轉(zhuǎn)到最后一個節(jié)點，然后將其移動到之前的頭節(jié)點并更新頭節(jié)點。讓我們先看一下代碼 -

// 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);

在上面的代碼中，我們使用了上面定義的基本函數(shù)鏈表的代碼，只是添加了一個新函數(shù)來旋轉(zhuǎn)鏈表。

在函數(shù)rotate中，我們首先使用while循環(huán)遍歷鏈表k次，并且在每次迭代中，我們都到達(dá)鏈表的倒數(shù)第二個元素。然后我們從鏈表中刪除鏈表的最后一個元素，并將其放在鏈表頭部之前的前面。最后，我們返回了新的頭，并使用顯示函數(shù)顯示了新的鏈表。

時間和空間復(fù)雜度

我們已經(jīng)移動了鏈表 k 次，鏈表的大小是 N，所以程序的整體時間復(fù)雜度是 O(N*K)。另外，我們沒有使用任何額外的空間，因此程序的空間復(fù)雜度是 O(1)，這是一個常數(shù)。

一次旋轉(zhuǎn)鏈表

在前面的代碼中，我們將元素逐一添加，這花費了 O(N*N) 的時間，以便我們可以更好地移動鏈表并獲取鏈表的大小。之后，我們將再次遍歷鏈表并獲取最后 k 個元素并將它們添加到鏈表的前面，這將使程序的時間復(fù)雜度為 O(1)。

結(jié)論

在本教程中，我們學(xué)習(xí)了如何在 JavaScript 編程語言中順時針旋轉(zhuǎn)鏈表。我們已經(jīng)看到了深入理解概念的代碼。 JavaScript 中鏈表的基本結(jié)構(gòu)可以使用 JavaScript 中的類創(chuàng)建，然后可以將節(jié)點從一個位置移動到另一個位置以進(jìn)行旋轉(zhuǎn)。程序的時間復(fù)雜度為O(N*N)，可以進(jìn)一步提高到O(N)，而程序的空間復(fù)雜度為O(1)。

以上是鏈表順時針旋轉(zhuǎn)的JavaScript程序的詳細(xì)內(nèi)容。更多信息請關(guān)注PHP中文網(wǎng)其他相關(guān)文章！