Viết chương trình kết hợp hai danh sách đã được sắp xếp bằng Python

Đề bài: Cho hai danh sách đã được sắp xếp gồm N và M nút tương ứng. Nhiệm vụ của bạn là kết hợp hai danh sách lại với nhau và trả về danh sách đã kết hợp theo thứ tự chuẩn.

Ví dụ:

Input: a: 5->10->15, b: 2->3->20
Output: 2->3->5->10->15->20

Input: a: 1->1, b: 2->4
Output: 1->1->2->4

Trong bài viết này, Quản Trị Mạng sẽ cùng các bạn tìm hiểu cách viết chương trình kết hợp hai danh sách đã được sắp xếp bằng Python và C++.

Cách 1: Sử dụng các nút giả

Ý tưởng của phương pháp này là sử dụng một nút giả tạm thời làm nút đầu tiên của danh sách kết quả. Con trỏ Tail luôn luôn trỏ tới nút cuối cùng trong danh sách kết quả nên vì thế việc thêm các nút mới trở nên dễ dàng hơn nhiều.

Bạn có thể xem lược đồ bên dưới để có thể dễ hình dung hơn:

Làm theo các bước sau để giải quyết vấn đề:

• Đầu tiên, tạo ra một nút giả cho danh sách kết quả hợp nhất.
• Bây giờ, tạo ra hai con trỏ, một con trỏ sẽ trỏ vào danh sách 1 (list1) và con trỏ còn lại trỏ vào danh sách 2 (list2).
• Bây giờ, duyệt qua cả hai danh sách cho tới khi chúng hết mọi nút.
• Nếu giá trị của một nút đang được trỏ đến trong một danh sách nhỏ hơn giá trị đang được trỏ trong danh sách kia, thêm nút đó vào danh sách kết quả hợp nhất và tăng con trỏ đó lên.

Dưới đây là code mẫu bằng ngôn ngữ Python để các bạn tham khảo:

""" Python program to merge two
sorted linked lists """
 
 
# Linked List Node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
# Create & Handle List operations
class LinkedList:
    def __init__(self):
        self.head = None
 
    # Method to display the list
    def printList(self):
        temp = self.head
        while temp:
            print(temp.data, end=" ")
            temp = temp.next
 
    # Method to add element to list
    def addToList(self, newData):
        newNode = Node(newData)
        if self.head is None:
            self.head = newNode
            return
 
        last = self.head
        while last.next:
            last = last.next
 
        last.next = newNode
 
 
# Function to merge the lists
# Takes two lists which are sorted
# joins them to get a single sorted list
def mergeLists(headA, headB):
 
    # A dummy node to store the result
    dummyNode = Node(0)
 
    # Tail stores the last node
    tail = dummyNode
    while True:
 
        # If any of the list gets completely empty
        # directly join all the elements of the other list
        if headA is None:
            tail.next = headB
            break
        if headB is None:
            tail.next = headA
            break
 
        # Compare the data of the lists and whichever is smaller is
        # appended to the last of the merged list and the head is changed
        if headA.data <= headB.data:
            tail.next = headA
            headA = headA.next
        else:
            tail.next = headB
            headB = headB.next
 
        # Advance the tail
        tail = tail.next
 
    # Returns the head of the merged list
    return dummyNode.next
 
 
# Create 2 lists
listA = LinkedList()
listB = LinkedList()
 
# Add elements to the list in sorted order
listA.addToList(5)
listA.addToList(10)
listA.addToList(15)
 
listB.addToList(2)
listB.addToList(3)
listB.addToList(20)
 
# Call the merge function
listA.head = mergeLists(listA.head, listB.head)
 
# Display merged list
print("Danh sách sau khi kết hợp là:")
listA.printList()
 
""" This code is contributed
by Debidutta Rath """

Code mẫu bằng C++:

/* C++ program to merge two sorted linked lists */
#include <bits/stdc++.h>
using namespace std;
 
/* Link list node */
class Node {
public:
    int data;
    Node* next;
};
 
/* pull off the front node of
the source and put it in dest */
void MoveNode(Node** destRef, Node** sourceRef);
 
/* Takes two lists sorted in increasing
order, and splices their nodes together
to make one big sorted list which
is returned. */
Node* SortedMerge(Node* a, Node* b)
{
    /* a dummy first node to hang the result on */
    Node dummy;
 
    /* tail points to the last result node */
    Node* tail = &dummy;
 
    /* so tail->next is the place to
    add new nodes to the result. */
    dummy.next = NULL;
    while (1) {
        if (a == NULL) {
            /* if either list runs out, use the
            other list */
            tail->next = b;
            break;
        }
        else if (b == NULL) {
            tail->next = a;
            break;
        }
        if (a->data <= b->data)
            MoveNode(&(tail->next), &a);
        else
            MoveNode(&(tail->next), &b);
 
        tail = tail->next;
    }
    return (dummy.next);
}
 
/* UTILITY FUNCTIONS */
/* MoveNode() function takes the
node from the front of the source,
and move it to the front of the dest.
It is an error to call this with the
source list empty.
 
Before calling MoveNode():
source == {1, 2, 3}
dest == {1, 2, 3}
 
After calling MoveNode():
source == {2, 3}
dest == {1, 1, 2, 3} */
void MoveNode(Node** destRef, Node** sourceRef)
{
    /* the front source node */
    Node* newNode = *sourceRef;
    assert(newNode != NULL);
 
    /* Advance the source pointer */
    *sourceRef = newNode->next;
 
    /* Link the old dest off the new node */
    newNode->next = *destRef;
 
    /* Move dest to point to the new node */
    *destRef = newNode;
}
 
/* Function to insert a node at
the beginning of the linked list */
void push(Node** head_ref, int new_data)
{
    /* allocate node */
    Node* new_node = new Node();
 
    /* put in the data */
    new_node->data = new_data;
 
    /* link the old list off the new node */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
/* Function to print nodes in a given linked list */
void printList(Node* node)
{
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}
 
/* Driver code*/
int main()
{
    /* Start with the empty list */
    Node* res = NULL;
    Node* a = NULL;
    Node* b = NULL;
 
    /* Let us create two sorted linked lists
    to test the functions
    Created lists, a: 5->10->15, b: 2->3->20 */
    push(&a, 15);
    push(&a, 10);
    push(&a, 5);
 
    push(&b, 20);
    push(&b, 3);
    push(&b, 2);
 
    /* Remove duplicates from linked list */
    res = SortedMerge(a, b);
 
    cout << "Danh sách sau khi kết hợp là: \n";
    printList(res);
 
    return 0;
}
 
// This code is contributed by rathbhupendra

Kết quả trả về là:

Danh sách sau khi kết hợp là: 
2 3 5 10 15 20 

Cách 2: Sử dụng đệ quy

Ý tưởng của phương pháp này là di chuyển về phía trước với một nút trong đệ quy có giá trị nút nhỏ hơn. Khi bất kỳ nút nào kết thúc, nối thêm phần còn lại của danh sách đã được liên kết.

Làm theo các bước sau để giải quyết vấn đề:

• Tạo một hàm trong đó có hai con trỏ trỏ đến danh sách sẽ được truyền vào.
• Sau đó, hãy kiểm tra xem hai nút được truyền vào nút nào có giá trị nhỏ hơn.
• Nút có giá trị nhỏ hơn thực hiện lệnh đệ quy bằng cách di chuyển về phía trước với con trỏ đỏ và đồng thời nối lệnh đệ quy với nút.
• Đồng thời đặt hai trường hợp cơ sở để kiểm tra xem một trong hai danh sách đã đạt tới giá trị NULL hay chưa sau đó nối phần còn lại của danh sách đã được liên kết vào.

Dưới đây là code mẫu để các bạn tham khảo:

# Python3 program merge two sorted linked
# in third linked list using recursive.
 
# Node class
 
 
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
 
 
# Constructor to initialize the node object
class LinkedList:
 
    # Function to initialize head
    def __init__(self):
        self.head = None
 
    # Method to print linked list
    def printList(self):
        temp = self.head
 
        while temp:
            print(temp.data, end=" ")
            temp = temp.next
 
    # Function to add of node at the end.
    def append(self, new_data):
        new_node = Node(new_data)
 
        if self.head is None:
            self.head = new_node
            return
        last = self.head
 
        while last.next:
            last = last.next
        last.next = new_node
 
 
# Function to merge two sorted linked list.
def mergeLists(head1, head2):
 
    # create a temp node NULL
    temp = None
 
    # List1 is empty then return List2
    if head1 is None:
        return head2
 
    # if List2 is empty then return List1
    if head2 is None:
        return head1
 
    # If List1's data is smaller or
    # equal to List2's data
    if head1.data <= head2.data:
 
        # assign temp to List1's data
        temp = head1
 
        # Again check List1's data is smaller or equal List2's
        # data and call mergeLists function.
        temp.next = mergeLists(head1.next, head2)
 
    else:
        # If List2's data is greater than or equal List1's
        # data assign temp to head2
        temp = head2
 
        # Again check List2's data is greater or equal List's
        # data and call mergeLists function.
        temp.next = mergeLists(head1, head2.next)
 
    # return the temp list.
    return temp
 
 
# Driver Function
if __name__ == '__main__':
 
    # Create linked list :
    list1 = LinkedList()
    list1.append(5)
    list1.append(10)
    list1.append(15)
 
    # Create linked list 2 :
    list2 = LinkedList()
    list2.append(2)
    list2.append(3)
    list2.append(20)
 
    # Create linked list 3
    list3 = LinkedList()
 
    # Merging linked list 1 and linked list 2
    # in linked list 3
    list3.head = mergeLists(list1.head, list2.head)
 
    print("Danh sách sau khi kết hợp là:")
    list3.printList()
 
 
# This code is contributed by 'Shriaknt13'.

Code mẫu bằng C++:

/* C++ program to merge two sorted linked lists */
#include <bits/stdc++.h>
using namespace std;
 
/* Link list node */
class Node {
public:
    int data;
    Node* next;
};
 
/* pull off the front node of
the source and put it in dest */
void MoveNode(Node** destRef, Node** sourceRef);
 
/* Takes two lists sorted in increasing
order, and splices their nodes together
to make one big sorted list which
is returned. */
Node* SortedMerge(Node* a, Node* b)
{
    Node* result = NULL;
 
    /* Base cases */
    if (a == NULL)
        return (b);
    else if (b == NULL)
        return (a);
 
    /* Pick either a or b, and recur */
    if (a->data <= b->data) {
        result = a;
        result->next = SortedMerge(a->next, b);
    }
    else {
        result = b;
        result->next = SortedMerge(a, b->next);
    }
    return (result);
}
 
/* UTILITY FUNCTIONS */
/* MoveNode() function takes the
node from the front of the source,
and move it to the front of the dest.
It is an error to call this with the
source list empty.
 
Before calling MoveNode():
source == {1, 2, 3}
dest == {1, 2, 3}
 
After calling MoveNode():
source == {2, 3}
dest == {1, 1, 2, 3} */
void MoveNode(Node** destRef, Node** sourceRef)
{
    /* the front source node */
    Node* newNode = *sourceRef;
    assert(newNode != NULL);
 
    /* Advance the source pointer */
    *sourceRef = newNode->next;
 
    /* Link the old dest off the new node */
    newNode->next = *destRef;
 
    /* Move dest to point to the new node */
    *destRef = newNode;
}
 
/* Function to insert a node at
the beginning of the linked list */
void push(Node** head_ref, int new_data)
{
    /* allocate node */
    Node* new_node = new Node();
 
    /* put in the data */
    new_node->data = new_data;
 
    /* link the old list off the new node */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
/* Function to print nodes in a given linked list */
void printList(Node* node)
{
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}
 
/* Driver code*/
int main()
{
    /* Start with the empty list */
    Node* res = NULL;
    Node* a = NULL;
    Node* b = NULL;
 
    /* Let us create two sorted linked lists
    to test the functions
    Created lists, a: 5->10->15, b: 2->3->20 */
    push(&a, 15);
    push(&a, 10);
    push(&a, 5);
 
    push(&b, 20);
    push(&b, 3);
    push(&b, 2);
 
    /* Remove duplicates from linked list */
    res = SortedMerge(a, b);
 
    cout << "Danh sách sau khi kết hợp là: \n";
    printList(res);
 
    return 0;
}
 
// This code is contributed by rathbhupendra

Kết quả trả về là:

Danh sách sau khi kết hợp là: 
2 3 5 10 15 20 

Cách 3: Sử dụng phương thức đảo ngược danh sách với ngôn ngữ C++

Ý tưởng của phương thức này là đầu tiên sẽ tiến hành đảo ngược cả hai danh sách đã cho và sau đó duyệt qua cả hai danh sách từ đầu đến cuối rồi so sánh các nút của hai danh sách. Tiếp đến, chèn nút có giá trị lớn hơn vào đầu danh sách kết quả. Theo cách này, chúng ta sẽ nhận được danh sách kết quả theo thứ tự tăng dần.

Làm theo các bước sau để giải quyết vấn đề:

• Khởi tạo danh sách kết quả là rỗng: head = NULL.
• Đặt "a" và "b" lần lượt là phần đầu của danh sách thứ nhất và danh sách thứ hai tương ứng.
• Đảo ngược cả hai danh sách.
• Khi (a !=NULL và b!=NULL):
  • Tìm giá trị lớn hơn của cả hai (giá trị "a" và "b" hiện tại).
  • Chèn giá trị lớn hơn của nút vào phía trước danh sách kết quả.
  • Tiếp tục với các nút lớn hơn trong danh sách.
• Nếu "b" trở thành NULL trước "a", hãy chèn tất cả các nút của "a" vào danh sách kết quả ngay từ đầu.
• Nếu "a" trở thành NULL trước "b", hãy chèn tất cả các nút của "b" vào danh sách kết quả ngay từ đầu.

Dưới đây là code mẫu bằng C++ để các bạn tham khảo:

/*Given two sorted linked lists consisting of N and M nodes
respectively. The task is to merge both of the list
(in-place) and return head of the merged list.*/
#include <bits/stdc++.h>
using namespace std;
 
/* Link list Node */
struct Node {
    int key;
    struct Node* next;
};
 
// Function to reverse a given Linked List using Recursion
Node* reverseList(Node* head)
{
    if (head->next == NULL)
        return head;
    Node* rest = reverseList(head->next);
    head->next->next = head;
    head->next = NULL;
    return rest;
}
 
// Given two non-empty linked lists 'a' and 'b'
Node* sortedMerge(Node* a, Node* b)
{
    // Reverse Linked List 'a'
    a = reverseList(a);
    // Reverse Linked List 'b'
    b = reverseList(b);
    // Initialize head of resultant list
    Node* head = NULL;
    Node* temp;
    // Traverse both lists while both of them
    // have nodes.
    while (a != NULL && b != NULL) {
        // If a's current value is greater than or equal to
        // b's current value.
        if (a->key >= b->key) {
            // Store next of current Node in first list
            temp = a->next;
            // Add 'a' at the front of resultant list
            a->next = head;
            // Make 'a' - head of the result list
            head = a;
            // Move ahead in first list
            a = temp;
        }
 
        // If b's value is greater. Below steps are similar
        // to above (Only 'a' is replaced with 'b')
        else {
            temp = b->next;
            b->next = head;
            head = b;
            b = temp;
        }
    }
 
    // If second list reached end, but first list has
    // nodes. Add remaining nodes of first list at the
    // beginning of result list
    while (a != NULL) {
        temp = a->next;
        a->next = head;
        head = a;
        a = temp;
    }
 
    // If first list reached end, but second list has
    // nodes. Add remaining nodes of second list at the
    // beginning of result list
    while (b != NULL) {
        temp = b->next;
        b->next = head;
        head = b;
        b = temp;
    }
    // Return the head of the result list
    return head;
}
 
/* Function to print Nodes in a given linked list */
void printList(struct Node* Node)
{
    while (Node != NULL) {
        cout << Node->key << " ";
        Node = Node->next;
    }
}
 
/* Utility function to create a new node with
   given key */
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->next = NULL;
    return temp;
}
 
/* Driver program to test above functions*/
int main()
{
    /* Start with the empty list */
    struct Node* res = NULL;
 
    /* Let us create two sorted linked lists to test
       the above functions. Created lists shall be
         a: 5->10->15->40
         b: 2->3->20  */
    Node* a = newNode(5);
    a->next = newNode(10);
    a->next->next = newNode(15);
    a->next->next->next = newNode(40);
 
    Node* b = newNode(2);
    b->next = newNode(3);
    b->next->next = newNode(20);
 
    /* merge 2 sorted Linked Lists */
    res = sortedMerge(a, b);
 
    cout << "Danh sách sau khi kết hợp là: " << endl;
    printList(res);
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)

Kết quả trả về là:

Danh sách sau khi kết hợp là: 
2 3 5 10 15 20 

Quản Trị Mạng mong rằng bài viết này sẽ có ích đối với các bạn.