JavaScript實現連結串列的順時針旋轉

---

JavaScript連結串列的基本結構可以使用JavaScript中的類來建立，然後可以透過節點位置的移動來實現旋轉。本文將學習如何在JavaScript程式語言中順時針旋轉連結串列。我們將透過程式碼深入理解這些概念。

給定問題中，我們有一個連結串列，需要將其順時針旋轉。這意味著，每次移動都要將最後一個元素放在第一個位置，如果需要旋轉k次，則需要將最後k個元素放在連結串列的頭節點之前。如之前所見，建立連結串列需要一個類來將資料和指向下一個元素的指標繫結在一起。

連結串列結構

示例

首先，我們將建立一個名為`node`的類，它將儲存當前節點的值和指向下一個節點的指標。之後，我們將建立一個`push`函式，它將幫助建立連結串列，最後，我們將建立一個`display`函式，它將幫助列印連結串列。讓我們先看看程式碼：

// 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`關鍵字在類的建構函式中建立了一個部分來儲存資料和指向下一個節點的指標。

之後，我們定義了一個`push`函式，它將接受兩個引數：第一個是連結串列的頭節點，第二個是我們想要新增到連結串列的新節點的資料。在函式中，我們建立了新節點並將其值儲存在其中。我們檢查頭節點是否為空（這意味著我們將新增第一個元素），如果是，我們將直接返回新節點；否則，我們將使用迴圈遍歷到連結串列的末尾，並將新節點新增到那裡。

問題的解決方法

建立類並定義必要的基本函式後，我們將轉到主函式，在主函式中，我們將定義一個函式來將最後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次，在每次迭代中，我們都到達了連結串列的倒數第二個元素。然後，我們從連結串列中刪除最後一個元素，並將其放在連結串列的前面，即頭節點之前。最後，我們返回新的頭節點，並使用`display`函式顯示新的連結串列。

時間和空間複雜度

我們遍歷了連結串列k次，連結串列的大小為N，因此程式的總體時間複雜度為O(N*K)。此外，我們沒有使用任何額外的空間，因此程式的空間複雜度為O(1)，即常數。

一次性旋轉連結串列

在之前的程式碼中，我們一次新增一個元素，這導致時間複雜度為O(N*N)。為了改進這一點，我們可以遍歷連結串列並獲取連結串列的大小。之後，我們將再次遍歷連結串列，獲取最後k個元素並將它們新增到連結串列的前面，這將使程式的時間複雜度變為O(N)。

結論

在本教程中，我們學習瞭如何在JavaScript程式語言中順時針旋轉連結串列。我們透過程式碼深入理解了這些概念。JavaScript連結串列的基本結構可以使用JavaScript中的類來建立，然後可以透過節點位置的移動來實現旋轉。程式的時間複雜度為O(N*N)，可以進一步改進為O(N)，而程式的空間複雜度為O(1)。