c++ 如何合并两个有序链表

合并两个有序链表是一个经典的算法问题。下面将详细讲解使用C++解决这个问题的完整攻略。

问题描述

合并两个有序链表为一个新的有序链表。

解决思路

迭代法

迭代法的思路是:比较两个链表的节点,将较小的节点加入合并后的链表,直到有一个链表为空。此时将另一个非空链表节点全部加入合并后的链表即可。

递归法

递归法的思路是:比较两个链表的头部,较小的节点加入合并后的链表,然后继续递归下去,更新链表头,直到有一个链表为空。此时将另一个非空链表节点全部加入合并后的链表即可。

选择使用哪种方法取决于个人喜好和算法效率。通常来说,迭代法的效率要高于递归法。

代码实现

迭代法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummyHead(0);
        ListNode* tail = &dummyHead;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }             
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        return dummyHead.next;
    }
};

递归法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l2->next, l1);
            return l2;
        }
    }
};

示例代码

#include <iostream>
#include <vector>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummyHead(0);
        ListNode* tail = &dummyHead;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }             
            tail = tail->next;
        }
        tail->next = l1 ? l1 : l2;
        return dummyHead.next;
    }
};

void printList(ListNode* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Solution s;
    vector<int> nums1 = {1, 3, 5, 7};
    vector<int> nums2 = {2, 4, 6, 8};
    ListNode* l1 = new ListNode(0);
    ListNode* l2 = new ListNode(0);
    ListNode* p = l1;
    for (int num : nums1) {
        p->next = new ListNode(num);
        p = p->next;
    }
    p = l2;
    for (int num : nums2) {
        p->next = new ListNode(num);
        p = p->next;
    }
    ListNode* merged = s.mergeTwoLists(l1->next, l2->next);
    printList(merged); // 1 2 3 4 5 6 7 8
    return 0;
}
#include <iostream>
#include <vector>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (!l1) return l2;
        if (!l2) return l1;
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l2->next, l1);
            return l2;
        }
    }
};

void printList(ListNode* head) {
    while (head) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

int main() {
    Solution s;
    vector<int> nums1 = {1, 3, 5, 7};
    vector<int> nums2 = {2, 4, 6, 8};
    ListNode* l1 = new ListNode(0);
    ListNode* l2 = new ListNode(0);
    ListNode* p = l1;
    for (int num : nums1) {
        p->next = new ListNode(num);
        p = p->next;
    }
    p = l2;
    for (int num : nums2) {
        p->next = new ListNode(num);
        p = p->next;
    }
    ListNode* merged = s.mergeTwoLists(l1->next, l2->next);
    printList(merged); // 1 2 3 4 5 6 7 8
    return 0;
}

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:c++ 如何合并两个有序链表 - Python技术站

(0)
上一篇 2023年5月23日
下一篇 2023年5月23日

相关文章

  • c++容器list、vector、map、set区别与用法详解

    C++容器list、vector、map、set区别与用法详解 C++容器是C++标准库提供的一些数据结构,包括vector、list、map、set等。这些容器在我们编写代码时,经常会被用到。针对不同的应用场景,我们会选择不同的容器。本文将对C++中常用的四种容器:list、vector、map、set做一个详细介绍,分别介绍其区别和用法。 List li…

    C 2023年5月22日
    00
  • Linux下g++编译与使用静态库和动态库的方法

    下面是针对“Linux下g++编译与使用静态库和动态库的方法”的完整攻略: 1. 编译静态库 1.1 静态库介绍 静态库是在程序编译阶段将库文件的代码全部加入到生成的可执行文件中,因此在程序运行时不需要再去加载这些库文件。另外,同一份静态库可以同时被多个程序使用,节省系统资源。 1.2 编译静态库的方法 编写样例程序如下: // test.cpp #incl…

    C 2023年5月23日
    00
  • C++AVL树4种旋转详讲(左单旋、右单旋、左右双旋、右左双旋)

    C++AVL树4种旋转详讲 什么是AVL树? AVL树是一种自平衡二叉搜索树,它在插入或删除一个节点时,会通过旋转操作进行自平衡。AVL树的特点是保证树的高度始终保持在O(logN)的水平,从而保证了树的查询、插入、删除等操作时间复杂度保持在O(logN)的水平。因此在大规模数据的场景下,使用AVL树能够取得很好的性能表现。 AVL树的基本操作 AVL树的基…

    C 2023年5月22日
    00
  • C++实现日期类(Date)

    下面是实现C++日期类(Date)的完整攻略: 1. 设计类的属性和方法 Date类需要包含年、月、日三个属性,因此我们可以设计如下的类定义: class Date { public: Date(int year = 1970, int month = 1, int day = 1); // 构造函数 void setYear(int year); // 设…

    C 2023年5月23日
    00
  • C/C++ Qt 数据库与TableView实现多组件联动

    下面我将为你详细讲解如何使用 C/C++ Qt 实现数据库和 TableView 的联动。 准备工作 在开始之前,我们需要先准备好以下工具和环境: Qt:这是一个跨平台的 C++ 应用程序开发框架,我们将使用 Qt 来开发我们的程序。 MySQL:一个关系型数据库管理系统,我们将使用它来存储和管理我们的数据。 Qt Creator:这是一个供 Qt 开发者使…

    C 2023年5月22日
    00
  • 一篇文章教你3分钟如何发布Qt程序

    一篇文章教你3分钟如何发布Qt程序 在开始这个教程之前,请确保你已经完成了Qt程序的开发,并且准备好将其发布出去。 步骤一:构建Qt程序 首先,我们需要构建我们的Qt程序,以便我们能够将其发布出去。我们可以使用Qt Creator来构建程序,具体步骤如下: 打开Qt Creator,并打开你的Qt项目。 点击“构建”菜单,选择“构建项目”选项。 等待构建完成…

    C 2023年5月23日
    00
  • C++如何判断一个数字是否为质数

    下面是C++判断一个数字是否为质数的完整攻略,包含两条示例说明。 什么是质数 在数论中,质数是指除了 1 和本身之外,不能被其它正整数整除的数。比如,2、3、5、7、11、13等是质数,而4、6、8、9等不是质数。 C++中判断一个数字是否为质数 C++中判断一个数字是否为质数的方法一般是通过判断这个数是否能被除了1和它本身之外的其它数整除。这种判断方法比较…

    C 2023年5月23日
    00
  • C/C++ 中extern关键字详解

    C/C++ 中extern关键字详解 在 C/C++ 中,extern 是一个很常见的关键字,常用于声明全局变量或函数。本文将对 extern 关键字进行详细讲解。 1. 变量声明 当在多个源文件中引用同一全局变量时,需要在其中一个源文件中定义该全局变量,然后在其它源文件中使用 extern 关键字声明该变量。这样确保了在多文件编译时,每个文件都将引用同一变…

    C 2023年5月23日
    00
合作推广
合作推广
分享本页
返回顶部