链表顺时针旋转的JavaScript程序-js教程-PHP中文网

链表顺时针旋转的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中文网其他相关文章！