สร้าง Linked List ใหม่จากสอง Linked List โดยเลือกค่าสูงสุดแต่ละตำแหน่งใน C++

บทนำ

บทช่วยสอนนี้จะสาธิตวิธีสร้าง Linked List ใหม่จากสอง Linked List ที่มีขนาดเท่ากัน โดยเลือกค่าสูงสุด (maximum) จากแต่ละตำแหน่งที่ตรงกัน

ขั้นตอนการแก้ปัญหา

1. กำหนดโครงสร้างโหนด (struct Node) สำหรับ Linked List
2. สร้าง Linked List สองตัวที่มีขนาดเท่ากัน
3. วนลูปผ่านทั้งสอง List พร้อมกัน
4. หาค่าสูงสุดจากโหนดที่ตำแหน่งตรงกัน
5. สร้างโหนดใหม่ด้วยค่าสูงสุดนั้นและนำไปต่อใน List ใหม่
6. พิมพ์ Linked List ใหม่ที่ได้

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

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

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

void insertNewNode(Node** root, int item) {
    Node *ptr, *temp;
    temp = new Node;
    temp->data = item;
    temp->next = NULL;
    if (*root == NULL) {
        *root = temp;
    } else {
        ptr = *root;
        while (ptr->next != NULL) {
            ptr = ptr->next;
        }
        ptr->next = temp;
    }
}

void printLinkedList(Node* root) {
    while (root != NULL) {
        cout << root->data << " -> ";
        root = root->next;
    }
    cout << "NULL" << endl;
}

Node* generateNewLinkedList(Node* root1, Node* root2) {
    Node *ptr1 = root1, *ptr2 = root2;
    Node* root = NULL;
    while (ptr1 != NULL) {
        int currentMax = ((ptr1->data < ptr2->data) ? ptr2->data : ptr1->data);
        if (root == NULL) {
            Node* temp = new Node;
            temp->data = currentMax;
            temp->next = NULL;
            root = temp;
        } else {
            insertNewNode(&root, currentMax);
        }
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return root;
}

int main() {
    Node *root1 = NULL, *root2 = NULL, *root = NULL;
    insertNewNode(&root1, 1);
    insertNewNode(&root1, 2);
    insertNewNode(&root1, 3);
    insertNewNode(&root1, 4);
    insertNewNode(&root2, 3);
    insertNewNode(&root2, 1);
    insertNewNode(&root2, 2);
    insertNewNode(&root2, 4);
    root = generateNewLinkedList(root1, root2);
    printLinkedList(root);
    return 0;
}

ผลลัพธ์

3 -> 2 -> 3 -> 4 -> NULL

สรุป

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