พิมพ์โหนดสลับกันของ Linked List ด้วย Recursion ใน C++

Linked List เป็นโครงสร้างข้อมูลเชิงเส้นที่จัดเก็บข้อมูลในหน่วยความจำไม่ต่อเนื่อง แต่ละโหนดมีข้อมูลและ Pointer ชี้ไปโหนดถัดไป

ปัญหา

กำหนด Linked List ให้พิมพ์เฉพาะโหนดสลับกัน (Alternate nodes) เช่น 1st, 3rd, 5th...

Input:  2 → 4 → 1 → 67 → 48 → 90
Output: 2 → 1 → 48

วิธีแก้: ใช้ Flag และ Recursion

ใช้ตัวแปร flag (0/1) สลับกัน พิมพ์เมื่อ flag=0 เรียกฟังก์ชันตัวเองพร้อม flag สลับ

โค้ดตัวอย่าง (Iterative Version จากต้นฉบับ)

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

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

void printAlternateNode(struct Node* head) {
    int flag = 0;
    while (head != NULL) {
        if (flag == 0) {
            printf(" %d ", head->data);
            flag = 1;
        } else {
            flag = 0;
        }
        head = head->next;
    }
}

void insertNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int main() {
    struct Node* head = NULL;
    insertNode(&head, 23);
    insertNode(&head, 4);
    insertNode(&head, 98);
    insertNode(&head, 5);
    insertNode(&head, 71);
    printAlternateNode(head);
    return 0;
}

ผลลัพธ์

71  98  23

(เพราะ Insert แบบ Push Front ทำให้ลำดับกลับ: 71→5→98→4→23 พิมพ์ index 0,2,4 → 71, 98, 23)

เวอร์ชัน Recursive (เพิ่มเติม)

void printAlternateRecursive(struct Node* head, bool print = true) {
    if (head == NULL) return;
    if (print) printf("%d ", head->data);
    printAlternateRecursive(head->next, !print);
}

ความซับซ้อน

• Time: O(n) - วิ่งผ่านทุกโหนดครั้งเดียว
• Space (Iterative): O(1)
• Space (Recursive): O(n) เรียก Stack