วิธีการเรียกซ้ำเพื่อหาโหนดที่ N จากท้ายใน Linked List ด้วย C++

ภาพรวม

เมื่อได้รับ Singly Linked List และจำนวนเต็มบวก N เป็นอินพุต เป้าหมายคือการหาโหนดที่ N จากท้ายของลิสต์โดยใช้การเรียกซ้ำ (Recursion) ตัวอย่าง: หากลิสต์มีโหนด a → b → c → d → e → f และ N = 4 โหนดที่ 4 จากท้ายจะเป็น c

วิธีการคือเดินไปจนถึงโหนดสุดท้าย แล้วขณะกลับจากการเรียกซ้ำ (Backtracking) เพิ่มตัวนับ เมื่อตัวนับเท่ากับ 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 จากท้าย

แนวทางการแก้ปัญหา

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

• สร้างโครงสร้าง Node ที่มี int data และ Node* next
• ฟังก์ชัน addtohead(Node** head, int data) ใช้เพิ่มโหนดที่หัวเพื่อสร้าง Singly Linked List
• สร้างลิสต์โดยใช้ฟังก์ชันข้างต้น
• ฟังก์ชัน display(Node* head) พิมพ์ลิสต์จากโหนดหัว
• รับ N เป็นจำนวนเต็มบวก
• ฟังก์ชัน findNode(Node* head, int n1) เรียก searchNthLast เพื่อหาโหนด
• ฟังก์ชัน searchNthLast(Node* head, int n1, Node** nlast) คืนพอยน์เตอร์ของโหนดที่ N จากท้าย
• ใช้ตัวแปร static int count นับขณะ Backtrack
• หาก head == NULL คืนค่า
• เรียกซ้ำด้วย head->next แล้วเพิ่ม count
• เมื่อ count == n1 ตั้ง *nlast = head
• พิมพ์ค่าของโหนดที่ nlast ชี้ไป

ตัวอย่างโค้ด C++

#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