首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

在C++中合并两个链表的问题

在C++中合并两个链表的问题可以通过以下方式解决:

  1. 创建一个新的链表,用于存储合并后的结果。
  2. 定义两个指针,分别指向两个链表的头节点。
  3. 比较两个链表当前节点的值,将较小的节点添加到新链表中,并将指针向后移动一位。
  4. 重复步骤3,直到其中一个链表的指针为空。
  5. 将另一个链表剩余的节点直接添加到新链表的末尾。
  6. 返回新链表作为合并后的结果。

以下是一个示例代码:

代码语言:txt
复制
#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0); // 创建一个虚拟头节点
    ListNode* curr = dummy; // 当前节点指针

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

    // 将剩余的节点直接添加到新链表的末尾
    if (l1) {
        curr->next = l1;
    }
    if (l2) {
        curr->next = l2;
    }

    ListNode* result = dummy->next; // 获取合并后的链表
    delete dummy; // 释放虚拟头节点的内存
    return result;
}

int main() {
    // 创建链表1: 1 -> 2 -> 4
    ListNode* l1 = new ListNode(1);
    l1->next = new ListNode(2);
    l1->next->next = new ListNode(4);

    // 创建链表2: 1 -> 3 -> 4
    ListNode* l2 = new ListNode(1);
    l2->next = new ListNode(3);
    l2->next->next = new ListNode(4);

    // 合并两个链表
    ListNode* mergedList = mergeTwoLists(l1, l2);

    // 输出合并后的链表
    ListNode* curr = mergedList;
    while (curr) {
        std::cout << curr->val << " ";
        curr = curr->next;
    }
    std::cout << std::endl;

    // 释放链表的内存
    curr = mergedList;
    while (curr) {
        ListNode* temp = curr;
        curr = curr->next;
        delete temp;
    }

    return 0;
}

这个问题的解决方案是通过比较两个链表的节点值,逐个将较小的节点添加到新链表中,直到其中一个链表的指针为空。最后,将剩余的节点直接添加到新链表的末尾。这样可以保证合并后的链表仍然是有序的。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

合并两个排序链表

题目:输入两个递增排序链表合并两个链表并使新链表结点仍然是按照递增排序。例如下图中链表1和链表2,则合并之后升序链表链表3所示。...注:链表1和链表2是两个递增排序链表合并两个链表得到升序链表链表3. 首先分析合并两个链表过程。我们分析从合并两个链表头结点开始。...剩余结点中,链表2头结点值小于链表1头结点值,因此链表2头结点是剩余结点头结点,把这个结点和之前已经合并链表尾结点链接起来。 继续合并两个链表剩余结点(图中虚线框所示)。...两个链表剩下结点依然是排序,因此合并两个链表步骤和前面的步骤是一样。我们还是比较两个头结点值。...每当代码试图访问空指针指向内存时程序就会崩溃,从而导致鲁棒性问题本题中,当第一个链表是空链表,也就是它头结点是一个空指针时,那么把它和第二个链表合并,显然合并结果是第二个链表

1K80

合并两个有序链表

题目:输入两个递增排序链表合并两个链表并使新链表节点仍然是递增排序。...这种链表 是需要我们遍历链表 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 是否需要头结点 : 因为我们 目前 头结点是不能确定 当l1.val<l=2.val...时 头结点指向l1 当l1.val>l2.val 时 头结点指向l2 因此我们需要一个头结点指向 头结点next 指向l1或l2 我们还需要判断边界条件 两个链表不一定一样长 有可能l1遍历完了...l2还没遍历完 或者l2遍历完了 l1还没遍历完 此时我们需要让 头节点next指向链表剩余元素 代码实现 class Solution { public ListNode mergeTwoLists...=null){ //如果l2链表不为空剩余加入到cur cur.next=l2; } return dump.next

35710

合并两个排序链表

前言 给定两个递增排序链表,如何将这两个链表合并合并链表依然按照递增排序。本文就跟大家分享一种解决方案,欢迎各位感兴趣开发者阅读本文。...同样,这个问题也可以用双指针思路来实现: p1指针指向链表1头节点 p2指针指向链表2头节点 声明一个变量存储合并链表,比对两个指针指向节点值大小: 如果p1指针指向节点值比p2指向值小...,合并链表节点就取p1节点值,p1指针继续向前走,进行下一轮比对 如果p2指针指向节点值比p1指向值小,合并链表节点就取p2节点值,p2指针继续向前走,进行下一轮比对 当p1节点指向...null时,合并链表节点就为p2所指向链表节点;当p2节点指向null时,合并链表节点就为p1所指向链表节点。...1 声明一个变量pMergedHead用于存储合并链表头节点 如果当前链表1节点值小于链表2节点值 pMergedHead值就为链表2节点值 pMergedHead下一个节点值就为链表1下一个节点和链表

82410

leetcode链表合并两个排序链表

序 本文主要记录一下leetcode链表合并两个排序链表 Sort-Linked-List.png 题目 输入两个递增排序链表合并两个链表并使新链表节点仍然是递增排序。 ​...{ cursor.next = l1; } ​ return newHead.next; } } 这里先创建一个newHead节点来表示合并链表头指针...,然后创建一个cursor,其初始值为newHead;之后同时遍历l1及l2,取最小作为cursor.next,同时该链表前进一个节点,并且cursor跟着前进;最后再将cursor.next指向尚未遍历完链表剩余节点...;之后返回头指针指向节点 小结 合并两个有序链表基本思路就是设置一个cursor以及新链表头指针,然后同时遍历两个链表,取小节点作为cursornext,然后该链表往前进,cursor也跟着往前进...,最后再将cursor.next指向尚未遍历完链表剩余节点 doc he-bing-liang-ge-pai-xu-de-lian-biao-lcof

62100

算法-合并两个排序链表

题目: 输入两个递增排序链表合并两个链表并使新链表结点仍然是按照递增顺序。例如输入链表1和链表2如下,合并链表3。...解题思路: 首先可以确定是,链表1和链表2本身就是递增,所以合并过程可以从链表1,2头结点开始,先比较1,2头结点中值大小,将小结点(比如为链表1头结点)作为合并链表链表3)...随后可以考虑成链表1从原链表第二个结点开始,再次重复上面的步骤,这样就变成了一个递归问题。 ? ? ?...个人感觉值得注意地方有下面几个: (1)如果链表1,2为空,要考虑代码鲁棒性。 (2)要考虑链表1,2某结点数值相等情况,这个else包含了。 ? (3)递归调用何时退出?...return pHead1; 这就是这个代码很巧妙地方,往往使一行代码两个甚至多个作用,我们举这样例子: 链表1 : 1 3 链表2 : 2 4 首先执行

814100

leetcode链表合并两个排序链表

序 本文主要记录一下leetcode链表合并两个排序链表 题目 输入两个递增排序链表合并两个链表并使新链表节点仍然是递增排序。...{ cursor.next = l1; } return newHead.next; } } 这里先创建一个newHead节点来表示合并链表头指针...,然后创建一个cursor,其初始值为newHead;之后同时遍历l1及l2,取最小作为cursor.next,同时该链表前进一个节点,并且cursor跟着前进;最后再将cursor.next指向尚未遍历完链表剩余节点...;之后返回头指针指向节点 小结 合并两个有序链表基本思路就是设置一个cursor以及新链表头指针,然后同时遍历两个链表,取小节点作为cursornext,然后该链表往前进,cursor也跟着往前进...,最后再将cursor.next指向尚未遍历完链表剩余节点 doc he-bing-liang-ge-pai-xu-de-lian-biao-lcof

44720

合并两个排序链表

【题目】 输入两个递增排序链表合并两个链表并使新链表节点仍然是依照递增排序。...---- 【分析】 合并链表,须要找到头结点,对照两个链表头结点后,确定头结点,再确定头结点下一个结点,循环递归的如前面一样操作确定每一个结点位置,同一时候考虑边界条件,假设两个链表为空。...则肯定无需合并了,就是空链表,假设一个链表为空,还有一个不为空,则返回不为空链表。...(node_t)); p->node_next = NULL; return p; } //链表后面插入结点 node_t *insert_back(node_ptr p , data_type...printf("\n"); node_t *merge_list = merge(list1->node_next, list2->node_next); printf("合并链表顺序为

41910

合并两个排序链表

1 问题 关于链表合并,常见类型有两种: 直接合并,没有什么规则: 将多个链表头尾相连合并成一个链表 有序链表合并成有序链表两个有序链表合并成一个有序链表。...这里我们将要解决问题是有序列表合并,在上课时候我们学习了如何直接合并两个链表,那么如果在合并同时还要注意顺序问题的话该如何解决呢?本篇周博客将讨论此问题。...2 方法 (1)判断空链表情况,只要有一个链表为空,那答案必定就是另一个链表了,就算另一个链表也为空。 (2)新建一个空表头后面连接两个链表排序后节点,两个指针分别指向两链表头。...(3)遍历两个链表都不为空情况,取较小值添加在新链表后面,每次只把被添加链表指针后移。...直接连在后面 if pHead1: cur.next = pHead1 else: cur.next = pHead2 #返回值去掉表头 # return head.next 3 结语 我们针对排序单链表合并问题

8610

【日拱一卒】链表——两个有序链表合并

需求 将两个升序链表合并为一个新升序链表并返回。 新链表是通过拼接给定两个链表所有节点组成。...,也就是将两个有序链表重新合并成一个整体有序链表。...思路就是挨个比较两个链表元素,谁更小就先取谁,然后记得将指针移到下一个节点,直到遍历完两个链表。...具体步骤如下 1、数据初始化 最终要返回一个有序合并链表,就需要先初始化一个结果链表,即result。 ? 2、遍历两个链表,比较大小 ?...这里有一个问题:如果直接使用result,第一个元素指向l1.Val后,需要移动到下一个节点来保存下一个节点值,那这个result指针就是一直变,直到两个链表遍历完成。

42520

LeetCode004|合并两个排序链表

0x01,题目简述 输入两个递增排序链表合并两个链表并使新链表节点仍然是递增排序。...0x02,示例 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 0x03,题解思路 循环判断两个链表是否为空,若其中一个为空,则直接返回另外一个链表,因为题意链表元素大小是有序...,使用一个哨兵节点进行数据接收,当其中一个链表为空,退出循环,有可能循环退出之后,其中一个链表还有剩余元素没有挂载链表后面,所以最后后面要重新进行判断一下。...0x04,题解程序 0x05,总结 这周就没怎么去写关于技术文文章了,一个是觉得适度放松和写作对自己有好处,没有必要将自己处于一个非常忙碌状态,今天写这篇文章主要还两个链表操作,其实抛开链表前后节点直接连接关系...,所以现在自己心里可以慢慢去做自己想做事情了,其它不多说了,这篇文章如果可以帮助到需要的人就好,其实还是对自己帮助最大,目前文章内容基本上都是自己整理已经完成内容,做下内容沉淀

30330
领券