วิธีการแบบเรียกซ้ำเพื่อค้นหาโหนดที่ n จากจุดสิ้นสุดในรายการที่เชื่อมโยงใน C++

กำหนดรายการเชื่อมโยงแบบเดี่ยวและจำนวนเต็มบวก N เป็นอินพุต เป้าหมายคือการค้นหาโหนดที่ N จากจุดสิ้นสุดในรายการที่กำหนดโดยใช้การเรียกซ้ำ หากรายการอินพุตมีโหนด a → b → c → d → e → f และ N เป็น 4 โหนดที่ 4 จากปลายสุดจะเป็น c

ก่อนอื่นเราจะสำรวจจนถึงโหนดสุดท้ายในรายการและในขณะที่กลับมาจากการนับการเรียกซ้ำ (ย้อนรอย) เมื่อการนับเท่ากับ N ให้ส่งคืนตัวชี้ไปยังโหนดปัจจุบันตามผลลัพธ์

ให้เราดูสถานการณ์อินพุตเอาต์พุตที่หลากหลายสำหรับสิ่งนี้ -

ป้อนข้อมูล − รายการ :- 1 → 5 → 7 → 12 → 2 → 96 → 33 N=3

ผลผลิต − โหนดที่ N จากโหนดสุดท้ายคือ:2

คำอธิบาย − โหนดสุดท้ายที่ 3 คือ 2.

ป้อนข้อมูล − รายการ :- 12 → 53 → 8 → 19 → 20 → 96 → 33 N=8

ผลผลิต − ไม่มีโหนด

คำอธิบาย − รายการมีเพียง 7 โหนดเท่านั้น ดังนั้นจึงไม่มีโหนดสุดท้ายที่ 8 ที่เป็นไปได้

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

ในแนวทางนี้ ก่อนอื่นเราจะไปถึงจุดสิ้นสุดของรายการโดยใช้การเรียกซ้ำ และในขณะที่ย้อนรอย เราจะเพิ่มตัวแปรการนับแบบคงที่ ทันทีที่การนับเท่ากับอินพุต N ให้ส่งคืนตัวชี้โหนดปัจจุบัน

• ใช้โครงสร้างโหนดที่มีส่วนข้อมูล int และโหนดเป็นตัวชี้ถัดไป

• ฟังก์ชัน addtohead(โหนด** head, int data) ใช้เพื่อเพิ่มโหนดในส่วนหัวเพื่อสร้างรายการที่เชื่อมโยงโดยลำพัง

• สร้างรายการที่เชื่อมโยงโดยลำพังโดยใช้ฟังก์ชันข้างต้นโดยมีส่วนหัวเป็นตัวชี้ไปยังโหนดแรก

• การแสดงฟังก์ชัน (หัวโหนด*) ใช้เพื่อพิมพ์รายการที่เชื่อมโยงโดยเริ่มจากโหนดหลัก

• ใช้ N เป็นจำนวนเต็มบวก

• ฟังก์ชัน findNode(หัวโหนด*, int n1) นำตัวชี้ไปที่ส่วนหัวและ n1 และพิมพ์ผลลัพธ์เมื่อพบโหนดที่ n1 จากจุดสิ้นสุด

• ใช้ blast เป็นตัวชี้ไปยังโหนดที่ n1 จากจุดสิ้นสุด

• เรียก searchNthLast(head, n1, &nlast) เพื่อค้นหาโหนดนั้น

• ฟังก์ชั่น searchNthLast(Node* head, int n1, Node** nlast) ส่งคืนตัวชี้ไปยังโหนดสุดท้ายที่ n1 จากจุดสิ้นสุดในรายการที่เชื่อมโยงโดยมีส่วนหัวเป็นโหนดแรก

• ใช้ตัวแปรการนับแบบคงที่

• หาก head เป็น NULL จะไม่ส่งคืนสิ่งใด

• ใช้ tmp=head->ต่อไป

• เรียก searchNthLast(tmp, n1, nlast) เพื่อวนซ้ำจนถึงโหนดสุดท้าย

• หลังจากนั้นจะเพิ่มขึ้นทีละ 1

• หากการนับเท่ากับ n1 ให้ตั้งค่า *nlast=head

• ในตอนท้ายพิมพ์ค่าของโหนดที่ชี้โดย nlast เป็นผลลัพธ์

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   Node* next;
};
void addtohead(Node** head, int data){
   Node* nodex = new Node;
   nodex->data = data;
   nodex->next = (*head);
   (*head) = nodex;
}
void searchNthLast(Node* head, int n1, Node** nlast){
   static int count=0;
   if (head==NULL){
      return;
   }
   Node* tmp=head->next;
   searchNthLast(tmp, n1, nlast);
   count = count + 1;
   if (count == n1){
      *nlast = head;
   }
}
void findNode(Node* head, int n1){
   Node* nlast = NULL;
   searchNthLast(head, n1, &nlast);
   if (nlast == NULL){
      cout << "Node does not exists";
   }
   else{
      cout << "Nth Node from the last is: "<< nlast->data;
   }
}
void display(Node* head){
   Node* curr = head;
   if (curr != NULL){
      cout<<curr->data<<" ";
      display(curr->next);
   }
}
int main(){
   Node* head = NULL;
   addtohead(&head, 20);
   addtohead(&head, 12);
   addtohead(&head, 15);
   addtohead(&head, 8);
   addtohead(&head, 10);
   addtohead(&head, 4);
   addtohead(&head, 5);
   int N = 2;
   cout<<"Linked list is :"<<endl;
   display(head);
   cout<<endl;
   findNode(head, N);
   return 0;
}

ผลลัพธ์

หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้

Linked list is :
5 4 10 8 15 12 20
Nth Node from the last is: 12