c++

C++单链表的合并操作如何实施

小樊
107
2024-07-16 20:25:47
栏目: 编程语言

在C++中,可以通过创建一个新的链表来合并两个已有的单链表。具体步骤如下:

  1. 创建一个新的链表用于存储合并后的结果。
  2. 遍历第一个链表,依次将节点复制到新链表中。
  3. 再遍历第二个链表,将节点依次复制到新链表的末尾。
  4. 最终返回新链表即为两个单链表合并后的结果。

下面是一个示例代码:

#include <iostream>

struct Node {
    int data;
    Node* next;
    Node(int val) : data(val), next(nullptr) {}
};

Node* mergeLists(Node* l1, Node* l2) {
    Node* dummy = new Node(0);
    Node* cur = dummy;

    while (l1 && l2) {
        if (l1->data < l2->data) {
            cur->next = l1;
            l1 = l1->next;
        } else {
            cur->next = l2;
            l2 = l2->next;
        }
        cur = cur->next;
    }

    cur->next = l1 ? l1 : l2;

    Node* mergedList = dummy->next;
    delete dummy;
    return mergedList;
}

void printList(Node* head) {
    Node* cur = head;
    while (cur) {
        std::cout << cur->data << " ";
        cur = cur->next;
    }
    std::cout << std::endl;
}

int main() {
    Node* l1 = new Node(1);
    l1->next = new Node(3);
    l1->next->next = new Node(5);

    Node* l2 = new Node(2);
    l2->next = new Node(4);
    l2->next->next = new Node(6);

    Node* mergedList = mergeLists(l1, l2);
    printList(mergedList);

    return 0;
}

在上面的示例代码中,我们首先定义了一个Node结构体表示链表节点,然后实现了mergeLists函数来合并两个有序单链表。最后在main函数中创建两个有序单链表,并调用mergeLists函数进行合并,然后输出合并后的链表。

0
看了该问题的人还看了