โปรแกรม C พิมพ์ k โหนดสุดท้ายของ Linked List เรียงกลับ (Recursive)

โจทย์

พิมพ์ k โหนดสุดท้ายของ Linked List เรียงจากท้ายมาหน้า โดยใช้วิธี Recursive (การเรียกซ้ำ)

ตัวอย่าง

Linked List: 29 → 34 → 43 → 56 → 88
k = 2
Output: 88 56

วิธีการ Recursive

1. เรียกฟังก์ชันตัวเองไปจนถึงท้ายลิสต์ (base case: head == NULL)
2. ขณะกลับมาจาก recursion (unwinding) เพิ่มตัวนับ count++
3. ถ้า count ≤ k ให้พิมพ์ข้อมูลโหนดปัจจุบัน
4. ทำให้พิมพ์ได้เฉพาะ k โหนดสุดท้าย เรียงจากท้ายมาหน้า

อัลกอริทึม

1. โครงสร้างโหนด struct node {int data; node* next;}
2. ฟังก์ชัน get(data) สร้างโหนดใหม่
3. ฟังก์ชัน lastval(head, count, k): if !head return; lastval(head->next, count, k); count++; if (count <= k) print head->data
4. main(): สร้างลิสต์ กำหนด k=2, count=0 เรียก lastval()

โค้ดภาษา C

#include <stdio.h>
#include <stdlib.h>

struct node {
    int data;
    node* next;
};

node* get(int data) {
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = data;
    newnode->next = NULL;
    return newnode;
}

void lastval(node* head, int& count, int k) {
    if (!head) return;
    lastval(head->next, count, k);
    count++;
    if (count <= k)
        printf("%d ", head->data);
}

int main() {
    node* head = get(11);
    head->next = get(243);
    head->next->next = get(321);
    head->next->next->next = get(421);
    head->next->next->next->next = get(522);
    
    int k = 2, count = 0;
    printf("last %d nodes of a list are :", k);
    lastval(head, count, k);
    return 0;
}

ผลลัพธ์

last 2 nodes of a list are : 522 421

หมายเหตุ: โค้ดใช้ int& count (C++ reference) ใน C ต้องใช้ pointer int* count แทน