Tạo danh sách liên kết mới từ hai danh sách bằng cách chọn phần tử lớn nhất tại mỗi vị trí trong C++

Giới thiệu

Trong hướng dẫn này, chúng ta sẽ viết chương trình C++ tạo danh sách liên kết mới từ hai danh sách liên kết đã cho, trong đó mỗi node của danh sách mới chứa giá trị lớn nhất từ hai node tương ứng của hai danh sách gốc.

Yêu cầu bài toán

• Hai danh sách liên kết có cùng kích thước
• Tạo danh sách mới với phần tử tại vị trí i là max(phần tử i của danh sách 1, phần tử i của danh sách 2)

Các bước thực hiện

1. Định nghĩa cấu trúc node cho danh sách liên kết
2. Tạo hai danh sách liên kết cùng kích thước với dữ liệu mẫu
3. Duyệt đồng thời qua hai danh sách
4. Tại mỗi vị trí, so sánh và lấy giá trị lớn hơn
5. Tạo node mới với giá trị max và thêm vào danh sách kết quả
6. In danh sách kết quả

Mã nguồn hoàn chỉnh

#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;
    
    // Tạo danh sách 1: 1 -> 2 -> 3 -> 4
    insertNewNode(&root1, 1);
    insertNewNode(&root1, 2);
    insertNewNode(&root1, 3);
    insertNewNode(&root1, 4);
    
    // Tạo danh sách 2: 3 -> 1 -> 2 -> 4
    insertNewNode(&root2, 3);
    insertNewNode(&root2, 1);
    insertNewNode(&root2, 2);
    insertNewNode(&root2, 4);
    
    root = generateNewLinkedList(root1, root2);
    printLinkedList(root);
    
    return 0;
}

Kết quả chạy chương trình

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

Giải thích kết quả

Phân tích độ phức tạp

• Thời gian: O(n) - duyệt qua n node của hai danh sách
• Không gian: O(n) - tạo danh sách mới có n node

Kết luận

Chương trình giải quyết bài toán bằng cách duyệt song song hai danh sách liên kết. Kỹ thuật này có thể mở rộng cho nhiều danh sách hoặc các phép toán khác (min, sum, etc.).