ในบทช่วยสอนนี้ เราได้รับรายการเชื่อมโยง A ที่มีความยาว N และจำนวนเต็ม 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 ต่อการวนซ้ำ (หรือวนซ้ำ) และบันทึกส่วนหัวและส่วนท้ายของโหนด K แต่ละคู่ในอินพุตที่กำหนด (รายการที่เชื่อมโยง) โดยใช้ตัวชี้การรวมและส่วนท้าย
-
จากนั้น กลับโหนด k ของรายการที่เชื่อมโยง และเข้าร่วมโหนดท้ายของรายการที่กลับรายการ โดยมีโหนดหลักของรายการที่เชื่อมโยงเริ่มต้น ซึ่งชี้โดยตัวชี้การรวม
-
จากนั้นเราจะเปลี่ยนตัวชี้ปัจจุบันเป็นโหนด k ถัดไป
-
ส่วนท้ายของรายการปกติตอนนี้ทำหน้าที่เป็นโหนดสุดท้าย (ซึ่งชี้โดยส่วนท้ายใหม่) และตัวชี้การรวมจะชี้ไปที่ส่วนหัวของรายการใหม่ (กลับด้าน) และรวมเข้าด้วยกัน เราจะทำซ้ำขั้นตอนเหล่านี้จนกว่าโหนดทั้งหมดจะทำตามขั้นตอนเดียวกัน
ตัวอย่าง
#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+1th
-
ย้อนกลับโหนด K ทั้งหมดที่ข้ามไป
-
ตั้งค่าตัวชี้ถัดไปของโหนดสุดท้ายของโหนด K คู่นั้นเป็นอุณหภูมิ
-
ข้ามการวนซ้ำถัดไปที่คู่ของโหนด 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++ เรายังเขียนโค้ดนี้ในภาษาจาวา ไพธอน และภาษาอื่นๆ ได้ด้วย ในแนวทางนี้ เราใช้การเรียกซ้ำเพื่อย้อนกลับโหนด K สำรองและข้ามโหนดที่เหลือ เราหวังว่าคุณจะพบว่าบทช่วยสอนนี้มีประโยชน์
