โปรแกรม C พิมพ์ Linked List เรียงกลับโดยไม่กลับลิสต์จริง (Recursive)

โจทย์

พิมพ์ Linked List เรียงจากท้ายมาหน้า (reverse order) แต่ ไม่เปลี่ยนลำดับโหนดจริง ใช้ Recursive

ตัวอย่าง

Input: 29 → 34 → 43 → 56
Output: 56 43 34 29

วิธีการ Recursive

1. ฟังก์ชัน reverse(head): ถ้า head == NULL return
2. เรียก reverse(head->next) ก่อน (ไปจนท้ายลิสต์)
3. พิมพ์ head->data (พิมพ์ขณะกลับมาจาก recursion)
4. ลำดับโหนดในหน่วยความจำไม่เปลี่ยนแปลง

อัลกอริทึม

1. โครงสร้างโหนด struct node {int data; node* next;}
2. ฟังก์ชัน reverse(node* head): base case head==NULL return; recursive call reverse(head->next); print head->data
3. ฟังก์ชัน push(&head, data) เพิ่มโหนดหน้าลิสต์
4. main(): push 4 ค่า เรียก reverse(head)

โค้ดภาษา C

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

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

void reverse(node* head) {
    if (head == NULL) return;
    reverse(head->next);
    printf("%d ", head->data);
}

void push(node** header, char newdata) {
    struct node* newnode = (struct node*)malloc(sizeof(struct node));
    newnode->data = newdata;
    newnode->next = (*header);
    (*header) = newnode;
}

int main() {
    node* head = NULL;
    push(&head, 56);
    push(&head, 43);
    push(&head, 34);
    push(&head, 29);
    reverse(head);
    return 0;
}

ผลลัพธ์

reverse of a linked list 56 43 34 29

ข้อดี: ไม่ต้องแก้ไข pointer ของลิสต์ ใช้ call stack จัดการลำดับการพิมพ์