Flattening a Linked List (รวม Linked List แบบเรียงลำดับ) ใน C++

ในปัญหานี้ เราได้รับ Linked List ที่แต่ละ Node มี 2 pointer:

• Right pointer: Node ถัดไปใน list หลัก
• Down pointer: Head ของ sub-linked-list ที่เรียงลำดับแล้ว

ทุก linked list เรียงลำดับอยู่แล้ว งานคือรวม (flatten) ให้กลายเป็น linked list เดียวที่เรียงลำดับ

ตัวอย่าง

Output: 1 → 4 → 5 → 6 → 7 → 8 → 11 → 12 → 16 → NULL

วิธีการแก้ปัญหา: Merge Sort for Linked List

Merge sub-lists แบบ recursive เพื่อรวมเป็น sorted list เดียว

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

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

class Node {
public:
    int data;
    Node *right, *down;
};

Node* mergeList(Node* a, Node* b) {
    if (!a) return b;
    if (!b) return a;
    Node* result;
    if (a->data < b->data) {
        result = a;
        result->down = mergeList(a->down, b);
    } else {
        result = b;
        result->down = mergeList(a, b->down);
    }
    result->right = NULL;
    return result;
}

Node* flattenLinkedList(Node* root) {
    if (!root || !root->right) return root;
    root->right = flattenLinkedList(root->right);
    return mergeList(root, root->right);
}

Node* push(Node* head, int data) {
    Node* newNode = new Node();
    newNode->data = data;
    newNode->right = NULL;
    newNode->down = head;
    return newNode;
}

int main() {
    Node* head = NULL;
    // สร้าง linked list ตัวอย่าง...
    head = flattenLinkedList(head);
    // print result...
    return 0;
}

ผลลัพธ์

1 => 4 => 5 => 6 => 7 => 8 => 11 => 12 => 16 => NULL