資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告