数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学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)。
浏览量：325
