数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 单链表中反转交替的 K 个节点
在本教程中，我们给定一个长度为 N 的链表 A 和一个整数 K。我们需要反转大小为 K 的节点对，这些节点对交替出现。还给定 N 可以被 K 整除。第一个参数是链表 A 的头指针，第二个参数是整数 K，例如
输入
5 -> 6 -> 2 -> 8 -> 5 -> 2 -> 4 -> 8 -> 9 -> 6 -> null K=2
输出
6 -> 5 -> 2 -> 8 -> 2 -> 5 -> 4 -> 8 -> 6 -> 9 -> null
输入
1 -> 2 -> 5 -> 8 -> 9 -> 6 -> 4 -> 5 -> 8 -> null K=3
输出
5 -> 2 -> 1 -> 8 -> 9 -> 6 -> 8 -> 5 -> 4 -> null
查找解决方案的方法
迭代解法
每次迭代（或循环）遍历 2K 个节点，并使用 join 和 tail 指针记录给定输入（链表）中每对 K 个节点的头和尾。
然后，反转链表的 k 个节点，并将反转列表的尾节点与 join 指针指向的初始链表的头节点连接起来。
然后我们将当前指针更改为下一个 k 个节点。
现在，普通列表的尾部充当最后一个节点（由 new tail 指向），而 join 指针将指向新的（反转的）列表的头，并将它们合并。我们将迭代这些步骤，直到所有节点都遵循相同的步骤。
示例
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
};
Node* kAltReverse(struct Node* head, int k){
Node* prev = NULL;
Node* curr = head;
Node* temp = NULL;
Node* tail = NULL;
Node* newHead = NULL;
Node* join = NULL;
int t = 0;
while (curr) {
t = k;
join = curr;
prev = NULL;
while (curr && t--) {
temp = curr->next;
curr->next = prev;
prev = curr;
curr = temp;
}
if (!newHead)
newHead = prev;
if (tail)
tail->next = prev;
tail = join;
tail->next = curr;
t = k;
while (curr && t--) {
prev = curr;
curr = curr->next;
}
tail = prev;
}
return newHead;
}
void push(Node** head_ref, int new_data){
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
void printList(Node* node){
int count = 0;
while (node != NULL) {
cout << node->data << " ";
node = node->next;
count++;
}
}
int main(void){
Node* head = NULL;
int i;
for (i = 6; i <27; i+=3)
push(&head, i);
int k = 3;
cout << "Given linked list \n";
printList(head);
head = kAltReverse(head, k);
cout << "\n Modified Linked list \n";
printList(head);
return (0);
}输出
Given linked list 24 21 18 15 12 9 6 Modified Linked list 18 21 24 15 12 9 6
递归解法
从起始位置遍历 K 个节点，并将 temp 值设置为第 k+1 个节点
反转遍历的所有 K 个节点。
将那对 K 个节点的最后一个节点的 next 指针设置为 temp。
跳过需要跳过的那对 K 个节点的下一轮迭代。
对于反转下一个 k 个节点，递归地遵循所有这些步骤，直到到达最后一个节点。
伪代码
reverseAltK(head, k) curr = head prev = null next = null count = 0 WHILE count < k AND curr next = curr.next curr.next = prev prev = curr curr = next count = count + 1 IF head head.next = curr count = 0 WHILE count < k-1 AND curr curr = curr.next count = count + 1 IF curr curr.next = reverseKGroupAltRecursive(curr.next, k) return prev
示例
#include <bits/stdc++.h>
using namespace std;
/* Link list node */
class node{
public:
int data;
node* next;
};
/* Helper function for kAltReverse() */
node * _kAltReverse(node *node, int k, bool b);
/* Alternatively reverses the given linked list
in groups of given size k. */
node *kAltReverse(node *head, int k){
return _kAltReverse(head, k, true);
}
/* Helper function for kAltReverse().
It reverses k nodes of the list only if
the third parameter b is passed as true,
otherwise moves the pointer k nodes ahead
and recursively calls iteself */
node * _kAltReverse(node *Node, int k, bool b){
if(Node == NULL)
return NULL;
int count = 1;
node *prev = NULL;
node *current = Node;
node *next;
/* The loop serves two purposes
1) If b is true,
then it reverses the k nodes
2) If b is false,
then it moves the current pointer */
while(current != NULL && count <= k){
next = current->next;
/* Reverse the nodes only if b is true*/
if(b == true)
current->next = prev;
prev = current;
current = next;
count++;
}
/* 3) If b is true, then node is the kth node.
So attach rest of the list after node.
4) After attaching, return the new head */
if(b == true){
Node->next = _kAltReverse(current, k, !b);
return prev;
}
/* If b is not true, then attach
rest of the list after prev.
So attach rest of the list after prev */
else{
prev->next = _kAltReverse(current, k, !b);
return Node;
}
}
/* UTILITY FUNCTIONS */
/* Function to push a node */
void push(node** head_ref, int new_data){
/* allocate node */
node* new_node = new node();
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print linked list */
void printList(node *node){
int count = 0;
while(node != NULL){
cout << node->data << " ";
node = node->next;
count++;
}
}
// Driver Code
int main(void){
/* Start with the empty list */
node* head = NULL;
int i;
// create a list 1->2->3->4->5...... ->20
for(i = 20; i > 0; i--)
push(&head, i);
cout << "Given linked list \n";
printList(head);
head = kAltReverse(head, 3);
cout << "\nModified Linked list \n";
printList(head);
return(0);
}输出
Given linked list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 Modified Linked list 3 2 1 4 5 6 9 8 7 10 11 12 15 14 13 16 17 18 20 19
结论
本教程教我们如何在单链表中反转交替的 k 个节点，以及 C++ 代码中的伪代码实现。我们也可以用 Java、Python 和其他语言编写此代码。在这种方法中，我们使用递归来反转交替的 K 个节点并跳过其余节点。希望本教程对您有所帮助。
更新于: 2022-03-07
277 次浏览
广告