精华内容
下载资源
问答
  • C++版本将两个有序链表合并为一个新的有序链表并返回原理及代码实现
  • 两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/merge-two-sorted-lists/ 著作权归领扣网络...

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/merge-two-sorted-lists/
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

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

    在这里插入图片描述

    展开全文
  • 1.题目要求 这是一道求职面试时经常... 输入:两个有序的单链表head1与head2;  输出:合并后的有序单链表mergeHead;  算法描述:  (1)如果head1或head2为空链表,则直接返回另外一个链表;  (2)选择h
  • 两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: 输入:l1 = [], l2 = [] 输出...

    将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

    示例 1:


    输入:l1 = [1,2,4], l2 = [1,3,4]
    输出:[1,1,2,3,4,4]
    示例 2:

    输入:l1 = [], l2 = []
    输出:[]
    示例 3:

    输入:l1 = [], l2 = [0]
    输出:[0]

    思路:
    递归,如果一个链表已经空了,那很自然,我们就返回另一个链表。

    如果说都没有空,我们来比较大小,返回小的,然后让下一个值与这次留下的值继续递归!

    代码:

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode() : val(0), next(nullptr) {}
     *     ListNode(int x) : val(x), next(nullptr) {}
     *     ListNode(int x, ListNode *next) : val(x), next(next) {}
     * };
     */
     //递归思想
    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            if(l1==nullptr) return l2;
            if(l2==nullptr) return l1;
            if(l1->val < l2->val){//如果l1的值小一些,就把下一个和l2送进去递归,然后把这个小的值输出
                l1->next = mergeTwoLists(l1->next,l2);
                return l1;
            }
            else{
                l2->next = mergeTwoLists(l1,l2->next);
                return l2;
            }
            return 0;
        }
    };

    展开全文
  • leetcode 21. 合并两个有序链表 C++

    千次阅读 2019-08-05 01:22:12
    两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 分析: 首先我想到的是...

    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

    示例:

    输入:1->2->4, 1->3->4
    输出:1->1->2->3->4->4

    分析:

      首先我想到的是l2插入到l1里面,并且使用前插法,使用前插法就需要一个头节点,我命名为Boss,boss->next = l1 进行链接,p指针指向待比较节点父节点,q指向待比较节点,接着循环判断比较l2->val和q->val的大小,如果q->val <= l2->val ,则将l2节点插入到l1里面,一直循环,知道出现一方为空。

      判空有两种情形,一种是l2先到达空节点,那么就说明l2的所有数据都成功插入,就直接退出循环并返回。

      第二种是l1先到达空节点,这就说明l2中还有数据,而且l2中的数据全部大于l1当前所有的数据,那么就只需要将l2链接进l1即可。

    改进:

      基本和上述相同,只不过用两个指针mn,m指向第一个小于p->val的值,n指向第一个大于q->val的值,插入时就插入m到n这一段,就减少了插入次数。我这里实现的是非改进版。。。。

      持续改进ing。。。。。

      

    /**
     * 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 *boss = new ListNode(0);
            if(NULL == l2 || NULL == l1)
                return NULL == l1?l2:l1;
            if(l2->val < l1->val)
                boss->val = l2->val;
            else
                boss->val = l1->val;
            boss->next = l1;
            //p指向待比较节点的父节点,q指向待比较节点
            ListNode *p,*q;
            p = boss;
            q = boss->next;
            while(NULL != l2){
                if(l2->val <= q->val){
                    //插到前面
                    p->next = l2;
                    p = p->next;
                    l2 = l2->next;
                    p->next  = q;
                    //注意,到了这里是不能将p,q指针往后移动的,要是实在不懂就画个图就一目了然了。
                }else{
                    p = q;
                    q = q->next;
                }
                if(NULL == q){
                    //注意,这里不能使用q = l2,这样会造成q与p断链
                    p->next = l2;
                    break;
                }
            }
            return boss->next;
        }
    };

     

    展开全文
  • 21.合并两个有序链表 写在前面,小白从零刷题,在解答会写出思路,正确答案,以及所有使用到的语法和知识点 1. 迭代 思路就是定义一个哨兵节点,然后判断l1和l2哪个小,指向小的,然后小的后移一位, class ...

    21.合并两个有序链表

    写在前面,小白从零刷题,在解答会写出思路,正确答案,以及所有使用到的语法和知识点

    1. 迭代

    1. 思路就是定义一个哨兵节点,然后判断l1和l2哪个小,指向小的,然后小的后移一位,

    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
            ListNode* preHead = new ListNode(-1);//定义一个新的节点,prehead指向它,此处保留方便之后用
            ListNode* prev = preHead;//定义一个指针指向它
            while (l1 != nullptr && l2 != nullptr) {//如果不空
                if (l1->val < l2->val) {
                    prev->next = l1;
                    l1 = l1->next;//连起来指向下一个节点
                } else {
                    prev->next = l2;
                    l2 = l2->next;//
                }
                prev = prev->next;
            }
            // 合并后 l1 和 l2 最多只有一个还未被合并完,我们直接将链表末尾指向未合并完的链表即可
            prev->next = l1 == nullptr ? l2 : l1;
    
            return preHead->next;//方便返回定义一个头节点
        }
    };
    

    2.不看答案写一次

    class Solution {
    public:
        ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    
            ListNode* dummy= new ListNode(0);
            ListNode* cur=dummy;
            while(l1!=nullptr&&l2!=nullptr)
            {
                if(l1->val<l2->val)
                {
                    cur->next=l1;
                    l1=l1->next;
                }
                else
                {
                    cur->next=l2;
                    l2=l2->next;
                }
                cur=cur->next;
            }   
            cur->next=l1==nullptr? l2:l1;//学习一下
            return dummy->next;//返回
        }
    };
    

    知识点

    1. C++11nullptr关键字
    展开全文
  • 两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1->2->4, 1->3->4 输出:1->1->2->3->4->4 C++代码如下: /** * ...
  • 合并两个有序链表 LeetCode21.合并两个有序链表 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 解法...
  • 题目:合并两个有序链表 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例 示例 1: 输入:l1 = [1,2,4], l2 = [1,3,4] 输出:[1,1,2,3,4,4] 示例 2: ...
  • 合并两个有序链表(三种方法)---C++实现

    万次阅读 多人点赞 2019-06-10 08:42:43
    //使用额外空间来合并链表 不对原始链表做改变 node* mergeTwoLinkListWithExtraPlace(node *head1, node *head2) { /*先创建一头结点 这里用任意的整数都可以 不一定用0 之后返回newHead->next 即可 该方法...
  • 题目描述 本题难度程度为简单,...C++解法 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Sol...
  • 合并两个有序链表 输入两个单调递增的有序链表,输出两个链表合并后的链表,当然合成后的链表满足单调非递减规则 题解: 1)指针法:对链表中的元素,用对两个链表设置两个指针,对有序链表的数据逐个进行比较,较小...
  • 两个有序(升序)的链表合并为一个新的有序的链表c++实现) 问题描述: 现有一个头结点为Ahead的A链表,如1->3->5->7,同时还有一个头结点为Bhead的B链表,如2->4->6->8->10->12。最终要...
  • C++ 合并两个有序链表

    2021-11-21 10:58:24
    虽然题目的意思是合并两个有序链表,但是要完全实现题目的意思首先我们需要先生成两个有序链表。一种简单的方式是建立两个链表然后手动有序赋值。但是感觉这样不是很好,所以这里我选择随机生成然后自动排序的方式...
  • 目录1. 题目2. 方法一2.1 代码2. 2结果 1. 题目 2. 方法一 2.1 代码 class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) ... ListNode *Link_min=l1,*Link_max=l2,*Temp;...
  • 题目 将两个有序链表合并为一个新的有序链表并返回。...题目要求合并两个有序链表成一个有序链表,我们可以建立一个新的链表,将两个链表的值一个一个插入到该链表中。 解决方案 迭代法: class Sol...
  • 题目:合并两个有序链表  将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例: 输入:1-&gt;2-&gt;4, 1-&gt;3-&gt;4 输出:1-&gt;1-...
  • 两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1-&gt;2-&gt;4, 1-&gt;3-&gt;4 输出:1-&gt;1-&gt;2-&gt;3-&...
  • 两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例: 输入:1-&gt;2-&gt;4, 1-&gt;3-&gt;4 输出:1-&gt;1-&gt;2-&gt;3-&...
  • 两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode...
  • 两个有序链表合并

    2019-03-14 11:16:17
    两个有序链表合并成一个链表合并后的链表仍然是有序的,依次输出合并后的链表的元素值,并求出第奇数位置元素之和
  • C++算法之 合并两个有序链表

    万次阅读 多人点赞 2014-12-05 11:39:51
    题目:合并两个已经排序好的链表 方法1: 两个链表   比如链表1: 1->3->5->7->9  链表2: 2->4->6->8->10  跟我们合并两个数组一样,链表1的头结点 和链表2的头节点比较,如果链表1头节点的值大于链表2头...
  • 题目描述:将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 代码: /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode ...
  • 合并2个有序链表三种方法 LeetCode OJ链接(戳我) 一般方法 有合并2个链表作为前提,再来看这题简直是简单,最简单容易想到该方法。 该方法固然可行,但是是两两合并链表,时间复杂度O(nk)(n是链表个数,k是链表长度...
  • 两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ...
  • leetcode 21 合并两个有序链表 C++
  • 两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例: 输入:1-&gt;2-&gt;4, 1-&gt;3-&gt;4 输出:1-&gt;1-&gt;2-&gt;3-&gt...
  • 两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例: 输入:1-&gt;2-&gt;4, 1-&gt;3-&gt;4 输出:1-&gt;1-&gt;2-&gt;3-&...
  • 思路2:函数名字中有merge 就该想到归并排序的合并部分,同时利用链表有序的特点 用一链表, 判断链表当前note的大小,如果小就挂到新链表上。最后返回新链表头即可 class Solution { public: ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,666
精华内容 4,666
关键字:

合并两个有序链表c++

c++ 订阅