資料結構
網路
關係資料庫管理系統 (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
