数据结构
网络
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 个浏览量
广告