Tạo danh sách liên kết mới từ hai danh sách cho trước với phần tử lớn hơn tại mỗi nút trong C++

Trong hướng dẫn này, chúng ta sẽ viết chương trình tạo danh sách liên kết mới từ hai danh sách liên kết cho trước.

Cho hai danh sách liên kết cùng kích thước, tạo danh sách liên kết mới từ hai danh sách với số lớn hơn tại mỗi nút tương ứng.

Các bước giải quyết

• Viết struct node.
• Tạo hai danh sách liên kết cùng kích thước.
• Duyệt qua danh sách liên kết:
  • Tìm số lớn hơn từ hai nút tương ứng.
  • Tạo nút mới với số lớn hơn đó.
  • Thêm nút mới vào danh sách mới.
• In danh sách liên kết mới.

Ví dụ

Xem mã nguồn dưới đây.

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

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

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

Node* getNewLinkedList(Node* root1, Node* root2) { 
    Node *ptr1 = root1, *ptr2 = root2, *ptr; 
    Node *root = NULL, *temp; 
    while (ptr1 != NULL) { 
        temp = new Node; 
        temp->next = NULL; 
        if (ptr1->data < ptr2->data) { 
            temp->data = ptr2->data; 
        } else { 
            temp->data = ptr1->data; 
        } 
        if (root == NULL) { 
            root = temp; 
        } else { 
            ptr = root; 
            while (ptr->next != NULL) { 
                ptr = ptr->next; 
            } 
            ptr->next = temp; 
        } 
        ptr1 = ptr1->next; 
        ptr2 = ptr2->next; 
    } 
    return root; 
} 

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

int main() { 
    Node *root1 = NULL, *root2 = NULL, *root = NULL; 
    insertNewNode(&root1, 1); 
    insertNewNode(&root1, 2); 
    insertNewNode(&root1, 3); 
    insertNewNode(&root1, 4); 
    cout << "First Linked List: "; 
    printLinkedList(root1); 
    insertNewNode(&root2, 0); 
    insertNewNode(&root2, 5); 
    insertNewNode(&root2, 2); 
    insertNewNode(&root2, 6); 
    cout << "Second Linked List: "; 
    printLinkedList(root2); 
    root = getNewLinkedList(root1, root2); 
    cout << "New Linked List: "; 
    printLinkedList(root); 
    return 0; 
}

Kết quả

Chạy mã trên sẽ cho kết quả:

First Linked List: 1->2->3->4->NULL
Second Linked List: 0->5->2->6->NULL
New Linked List: 1->5->3->6->NULL

Kết luận

Nếu bạn có thắc mắc về hướng dẫn này, hãy để lại bình luận.