JavaScript 旋转链表的程序

使用JavaScript中的类可以创建JavaScript中的链表的基本结构，然后可以通过将节点从一个位置移动到另一个位置来进行旋转。在本文中，我们将学习如何使用JavaScript编程语言以顺时针的方式旋转链表。我们将看到深入理解概念的代码。

在给定的问题中，我们给出了一个链表，我们必须按顺时针方向旋转它。这意味着，我们必须在每次移动中将最后一个元素放在第一个位置，并且如果给出我们必须旋转k次，那么我们必须将最后k个元素放在头部或链表的起始节点之前。为了创建一个链表，我们之前已经看到，我们需要一个将数据和指针绑定到下一个元素的类。

链表的结构

示例

首先，我们将创建一个类节点，用于存储当前节点的值和指向下一个节点的指针。之后，我们将创建一个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);

在上面的代码中，我们使用了上面定义的链表基本函数的代码，并添加了一个新的函数来旋转链表。

在旋转函数中，我们首先使用while循环对链表进行k次循环，在每次迭代中，我们都去了链表的倒数第二个元素。然后，我们从链表中删除了最后一个元素，并将其放在链表之前，即在头部之前。最后，我们返回了新的头部，并使用display函数显示了新的链表。

时间和空间复杂度

我们已经遍历了链表k次，链表的大小为N，因此该程序的总时间复杂度为O（N * K）。此外，我们没有使用任何额外的空间，因此程序的空间复杂度为O（1），即常数。

一次性旋转链表

在上一个代码中，我们一个一个地添加元素，这样会花费O（N * N）的时间，为了改进，我们可以遍历链表并获取链表的大小。然后，我们再次遍历链表并获取最后k个元素，并将它们添加到链表的前面，这将使程序的时间复杂度为O（1）。

结论

在本教程中，我们学习了如何使用JavaScript编程语言以顺时针方式旋转链表。我们已经看到了用于深入理解概念的代码。可以使用JavaScript中的类来创建JavaScript中链表的基本结构，然后可以通过节点从一个位置移动到另一个位置来进行旋转。该程序的时间复杂度为O（N * N），可以进一步改进为O（N），而程序的空间复杂度为O（1）。