数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学JavaScript程序：旋转双向链表N个节点
双向链表是一种线性数据结构，其中每个节点都存储着下一个节点和上一个节点的地址。给定一个双向链表，我们需要将其旋转N个节点，并打印结果。N是一个正数，并且小于或等于链表中节点的数量。
题目没有指定旋转的方向。因此，我们将演示双向链表的顺时针和逆时针两种旋转方式。
逆时针旋转双向链表
我们需要将双向链表的节点逆时针旋转给定次数 (N)。对于位于边缘的节点，我们将假设双向链表是一个循环，然后将最后一个节点移动到第一个节点（表头）的位置。我们将实现一个带有解释的代码来实现该算法。
示例
假设我们有一个双向链表：
LL = [1, 2, 3, 4, 5, 6, 7]
节点旋转次数为3
输出
旋转后的LL = [5, 6, 7, 1, 2, 3, 4]
示例
在下面的例子中，我们将一个双向链表逆时针旋转3个节点。
输入: 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7 <=> 8 -> null
预期输出: 6 <=> 7 <=> 8 <=> 1 <=> 2 <=> 3 <=> 4 <=> 5 -> null
// class to create the structure of the nodes
class Node{
constructor(data) {
this.value = data;
this.next = null;
this.prev = null;
}
}
// function to print the linked list
function print(head){
var temp = head;
var ans = ""
while(temp.next != null){
ans += temp.value;
ans += " <=> "
temp = temp.next
}
ans += temp.value
ans += " -> null"
console.log(ans)
}
// function to add data in linked list
function add(data, head, tail){
var new_node = new Node(data);
if(head == null){
head = new_node
return new_node
}
else{
tail.next = new_node;
new_node.prev = tail
return new_node
}
}
// function to rotate the linked list
function rotate(head, rotations){
var temp = head;
// getting length of the linked list
var len = 0;
while(temp != null){
len++;
temp = temp.next;
}
temp = head;
var mid = temp;
for(var i=0;i<len-rotations;i++){
mid = mid.next;
}
mid.prev.next = null
head = mid
head.prev = null
while(mid.next != null){
mid = mid.next;
}
mid.next = temp;
return head;
}
// defining linked list
var head = new Node(1)
var tail = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
tail = add(7,head, tail)
tail = add(8,head, tail)
// given number
number = 3;
console.log("The given linked list is: ")
print(head)
console.log("The given linked list after 3 rotations is: ")
head = rotate(head,number)
print(head)
输出
The given linked list is: 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7 <=> 8 -> null The given linked list after 3 rotations is: 6 <=> 7 <=> 8 <=> 1 <=> 2 <=> 3 <=> 4 <=> 5 -> null
顺时针旋转双向链表
我们需要将双向链表的节点顺时针旋转给定次数 (N)。对于位于边缘的节点，我们将假设双向链表是一个循环，然后将最后一个节点移动到第一个索引位置。我们将实现一个带有解释的代码来实现该算法。
示例
假设我们有一个双向链表：
LL = [1, 2, 3, 4, 5, 6, 7]
节点旋转次数为3
输出
旋转后的LL = [4, 5, 6, 7, 1, 2, 3]
示例
在下面的例子中，我们将一个双向链表顺时针旋转3个节点。
输入: 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7 <=> 8 -> null
预期输出: 4 <=> 5 <=> 6 <=> 7 <=> 8 <=> 1 <=> 2 <=> 3 -> null
// class to create the structure of the nodes
class Node{
constructor(data){
this.value = data;
this.next = null;
this.prev = null;
}
}
// function to print the linked list
function print(head){
var temp = head;
var ans = ""
while(temp.next != null){
ans += temp.value;
ans += " <=> "
temp = temp.next
}
ans += temp.value
ans += " -> null"
console.log(ans)
}
// function to add data in linked list
function add(data, head, tail){
var new_node = new Node(data);
if(head == null){
head = new_node
return new_node
}
else{
tail.next = new_node;
new_node.prev = tail
return new_node
}
}
// function to rotate the linked list
function rotate(head, rotations){
var temp = head;
// getting length of the linked list
var len = 0;
while(temp != null){
len++;
temp = temp.next;
}
temp = head;
var mid = temp;
for(var i=0;i<rotations;i++){
mid = mid.next;
}
mid.prev.next = null
head = mid
head.prev = null
while(mid.next != null){
mid = mid.next;
}
mid.next = temp;
return head;
}
// defining linked list
var head = new Node(1)
var tail = head
tail = add(2,head, tail)
tail = add(3,head, tail)
tail = add(4,head, tail)
tail = add(5,head, tail)
tail = add(6,head, tail)
tail = add(7,head, tail)
tail = add(8,head, tail)
// given number
number = 3;
console.log("The given linked list is: ")
print(head)
console.log("The given linked list after 3 rotations is: ")
head = rotate(head, number)
print(head)
输出
The given linked list is: 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7 <=> 8 -> null The given linked list after 3 rotations is: 4 <=> 5 <=> 6 <=> 7 <=> 8 <=> 1 <=> 2 <=> 3 -> null
结论
在本教程中，我们实现了JavaScript程序，用于在顺时针和逆时针两个方向上旋转双向链表给定的次数，无需使用任何额外空间，时间复杂度为线性。
浏览量：177
