資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究用於在單鏈表中反轉交替的 K 個節點的 JavaScript 程式
連結串列反轉是指按照相反的方式排列連結串列中的所有節點，就像它們之前存在的順序相反一樣，或者將連結串列最後部分的元素移動到頭部，將頭部節點移動到尾部。按照交替方式反轉 K 個節點是指，反轉前 K 個元素，然後保持接下來的 K 個元素不變，再反轉接下來的 K 個元素，以此類推。我們將看到針對每種方法的不同程式碼和說明。
例如
If the given linked list is the: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> 11 -> null If the given value of k is 3 Output: 3 -> 2 -> 1 -> 4 -> 5 -> 6 -> 9 -> 8 -> 7 -> 10 -> 11 -> null
示例：迭代法
// class to create the structure of the nodes
class Node{
constructor(data) {
this.value = data;
this.next = 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){
return tail.next = new Node(data);
}
// function to remove the duplicate numbers
function reverseGroup(head, number){
if (!head || number == 1){
return head;
}
var temp = new Node();
temp.value = -1;
temp.next = head;
var prev = temp;
var cur = temp;
var next = temp;
// Calculating the length of linked list
var len = 0;
while (cur) {
len++;
cur = cur.next;
}
// Iterating till next is not NULL
while(prev) {
cur = prev.next;
next = cur.next;
var toL = len > number ? number : len - 1;
for (var i = 1; i < toL; i++){
cur.next = next.next;
next.next = prev.next;
prev.next = next;
next = cur.next;
}
prev = cur;
len -= number;
// skiping the next elements
var num = number;
while(num && prev != null){
num--;
prev = prev.next
}
}
return temp.next;
}
// 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)
tail = add(9,head, tail)
tail = add(10,head, tail)
tail = add(11,head, tail)
// given number
var number = 3
console.log("The given linked list is: ")
print(head)
// calling function to reverse elements in group
head = reverseGroup(head,number)
console.log("The Linked list after reversing elements in alternative groups is: ")
print(head)
示例：遞迴法
// class to create the structure of the nodes
class Node{
constructor(data){
this.value = data;
this.next = 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){
return tail.next = new Node(data);
}
// function to remove the duplicate numbers
function reverseGroup(head, number, move){
if (head == null) {
return null;
}
var cur = head;
var next = null;
var prev = null;
var cnt = 0;
while (cnt < number && cur != null){
next = cur.next;
if(move){
cur.next = prev;
}
prev = cur;
cur = next;
cnt++;
}
if(move){
head.next = reverseGroup(cur,number, !move)
return prev;
} else {
prev.next = reverseGroup(cur, number, !move);
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)
tail = add(9,head, tail)
tail = add(10,head, tail)
tail = add(11,head, tail)
// given number
var number = 3
console.log("The given linked list is: ")
print(head)
// calling function to reverse elements in group
head = reverseGroup(head,number,true)
console.log("The Linked list after reversing elements in alternative groups is: ")
print(head)
結論
在本教程中，我們使用 JavaScript 程式語言針對以交替 K 元素為一組反轉給定連結串列實現了兩方法。我們的程式碼的時間複雜度為 O(1)，迭代程式碼採用 O(1) 空間複雜度，而遞迴法採用 O(N)。
更新於： 2023 年 4 月 12 日
108 個瀏覽量
廣告