Flatten Multilevel Linked List ใน C++

ในปัญหานี้ เราได้รับ Multilevel Linked List ซึ่งแต่ละ Node มี 2 pointer: next (node ถัดไปในระดับเดียวกัน) และ child (head ของ sub-list) งานคือ flatten ให้ node ระดับแรกมาก่อน ตามด้วยระดับที่ 2, 3, ...

ตัวอย่างโครงสร้าง

Output: 1 9 8 4 6 7 3 2 5

วิธีการแก้ปัญหา: Level Order Traversal แบบปรับเปลี่ยน

1. Traverse linked list ระดับแรกจนถึง tail
2. ถ้าเจอ child pointer → ย้าย child list ไปต่อที่ tail
3. อัปเดต tail pointer
4. ทำซ้ำสำหรับทุก node

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

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

class Node {
public:
    int data;
    Node *next, *child;
};

Node* createList(int* arr, int n) {
    Node *head = NULL, *p = NULL;
    for (int i = 0; i < n; i++) {
        if (!head) head = p = new Node();
        else { p->next = new Node(); p = p->next; }
        p->data = arr[i];
        p->next = p->child = NULL;
    }
    return head;
}

void flattenLinkedList(Node* head) {
    if (!head) return;
    Node* tail = head;
    while (tail->next) tail = tail->next;
    
    Node* cur = head;
    while (cur != tail) {
        if (cur->child) {
            tail->next = cur->child;
            Node* tmp = cur->child;
            while (tmp->next) tmp = tmp->next;
            tail = tmp;
        }
        cur = cur->next;
    }
}

int main() {
    // สร้าง multilevel list...
    flattenLinkedList(head);
    // print...
    return 0;
}

ผลลัพธ์

The flattened Linked List is 1 9 8 4 6 7 3 2 5