การแทรกและเรียงลำดับ Linked List แบบเรียกซ้ำใน C++

ภาพรวม

ได้รับค่าจำนวนเต็มที่จะนำมาสร้าง Linked List งานคือการแทรกและเรียงลำดับ (Traverse) Singly Linked List โดยใช้วิธีการเรียกซ้ำ (Recursive)

การแทรกโหนดที่ท้ายแบบเรียกซ้ำ

• หาก head เป็น NULL → แทรกโหนดที่ head
• มิฉะนั้น แทรกที่ head→next

การเรียงลำดับโหนดแบบเรียกซ้ำ

• หาก head เป็น NULL → จบการทำงาน
• มิฉะนั้น พิมพ์ head→data แล้วเรียก traverseList(head→next)

ตัวอย่าง

อินพุต − 1 - 2 - 7 - 9 - 10

เอาต์พุต − Linked list: 1 → 2 → 7 → 9 → 10 → NULL

อินพุต − 12 - 21 - 17 - 94 - 18

เอาต์พุต − Linked list: 12 → 21 → 17 → 94 → 18 → NULL

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

ใช้ฟังก์ชันแทรกโหนดและเรียงลำดับ Singly Linked List เรียกซ้ำสำหรับอินพุตถัดไป

• โครงสร้าง SLLNode มี int data และ SLLNode* next
• ฟังก์ชัน addtoEnd(SLLNode* head, int data) แทรกโหนดที่ท้ายลิสต์
• หาก head เป็น NULL สร้างโหนดใหม่ ตั้งค่า next เป็น NULL คืนพอยน์เตอร์โหนดนี้
• หาก head ไม่เป็น NULL เรียก head->next = addtoEnd(head->next, data)
• ฟังก์ชัน traverseList(SLLNode* head) เริ่มจาก head พิมพ์ค่าแต่ละโหนด
• หาก head เป็น NULL พิมพ์ "NULL" คืนค่า
• มิฉะนั้น พิมพ์ data เรียก traverseList(head->next)
• ใน main สร้างลิสต์ด้วย addtoEnd() พิมพ์ด้วย traverseList()

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

#include <bits/stdc++.h> 
using namespace std; 

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

SLLNode* addtoEnd(SLLNode* head, int data){ 
    if (head == NULL){ 
        SLLNode *nodex = new SLLNode; 
        nodex->data = data; 
        nodex->next = NULL; 
        return nodex; 
    } else { 
        head->next = addtoEnd(head->next, data); 
    } 
    return head; 
} 

void traverseList(SLLNode* head){ 
    if (head == NULL){ 
        cout << "NULL"; 
        return; 
    } 
    cout << head->data << " -> "; 
    traverseList(head->next); 
} 

int main(){ 
    SLLNode* head1 = NULL; 
    head1 = addtoEnd(head1, 1); 
    head1 = addtoEnd(head1, 8); 
    head1 = addtoEnd(head1, 56); 
    head1 = addtoEnd(head1, 12); 
    head1 = addtoEnd(head1, 34); 
    cout << "Linked List is :" << endl; 
    traverseList(head1); 
    return 0; 
}

ผลลัพธ์

Linked List is : 1 -> 8 -> 56 -> 12 -> 34 -> NULL