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

很简洁的递归，点赞！

牛的

厉害!!!

我的跟你的代码一样，但是只写了一行

return !l1?l2:(!l2?l1:(l1->val<l2->val?(l1->next=merge(l1->next,l2),l1):(l2->next=merge(l1,l2->next),l2)));

l1->next = merge(l1->next, l2);
大佬，这个递归语句是啥意思？

就是l1的下个节点指向将其他节点合并后的头节点

优美

你就离谱

e，我习惯性压行，经常一行几百字符，所以感觉这还好（

几百？

感受一下我曾经写过的不算压行严重的代码

#include<bits/stdc++.h>
using namespace std;
int a[8],ans;
int main(){
    while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6],a[1]||a[2]||a[3]||a[4]||a[5]||a[6]) ans=a[6]+a[5]+a[4]+((a[3]+3)>>2),a[1]=a[1]>11*a[5]?a[1]-11*a[5]:0,a[4]*5>a[2]?(a[1]=max(a[1]-((a[4]*5-a[2])<<2),0),a[2]=0):a[2]-=a[4]*5,a[3]&=3,a[3]==1?(a[2]>5?(a[2]-=5,a[1]=max(a[1]-7,0)):(a[1]=max(a[1]-27+(a[2]<<2),0),a[2]=0)):(a[3]==2?(a[2]>3?(a[2]-=3,a[1]=max(a[1]-6,0)):(a[1]=max(a[1]-18+(a[2]<<2),0),a[2]=0)):(a[3]==3&&(a[2]?(--a[2],a[1]=max(a[1]-5,0)):(a[1]=max(a[1]-9,0))))),ans+=(a[2]+8)/9,(a[2]=9-a[2]%9)!=9&&(a[1]=max(a[1]-36+(a[2]<<2),0)),cout<<ans+(a[1]+35)/36<<"\n";
    return 0;
}

花的

兄弟们，走过路过不要错过，精简版本瞅一瞅
精简递归

class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if(!l1 || !l2) return l1 ? l1 : l2;
        if(l1->val > l2->val) swap(l1, l2);
        l1->next = merge(l1->next, l2);
        return l1;
    }
};

精简迭代

class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(0);
        auto head = dummy;
        while(l1 && l2){
            if(l1->val > l2->val) swap(l1, l2);
            head->next = l1;
            l1 = l1->next;
            head = head->next;
        }
        head->next = l1 ? l1 : l2;
        return dummy->next;
    }
};

大师 谢谢你的分享

这个swap（）没有定义啊。

好像yxc总这里没有递归的版本，我街楼贴一下这题的递归版本吧，供大家参考

/**
 * 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 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        ListNode* res = dfs(l1, l2);
        return res;
    }
    ListNode* dfs(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) return l2;
        if (l2 == nullptr) return l1;
        ListNode* temp = nullptr;
        if (l1->val < l2->val) {
            temp = l1;
            temp->next = dfs(l1->next, l2);
        }
        else {
            temp = l2;
            temp->next = dfs(l1, l2->next);
        }
        return temp;
    }
};

代码在acwing 和 leetcode上都AC 了

棒！

赞

优秀！

tql

cur不是尾节点吗，为什么最后不需要cur=cur->next 将cur移动到最后呢，现在不是等于cur的下一个节点是l1/l2，而cur是上一个节点（倒数第二个）吗。

假设链表l1未遍历完成， l2已结束遍历，此时指针p指向l1接下来要链接的结点，我们的目的是按序链接两个链表由于l1各个结点依次连接， 只需要把cur 指向到p，它后面已经链接好了， 就不用往后移动cur了

#$\color{white}{y总nb}$

倒数第二句秒哇，同时完美的解决了同为空和两种一空一实的情况。

有没有大佬知道while里每一次要更新这个cur指针到最新的位置 但是后面单独判断l1还是l2不是空链表往dummy里加入 这个时候cur->next的值赋了 但是却不需要再cur = cur -> next 这是为什么

到后面单独判断l1还是l2不是空链表 这一步的时候已经是到最后一个（l1 或 l2 中还剩一个值） 后面没值啦 也就不需要cur = cur -> next来移动了

我已经想明白了 l1 或 l2 中并不一定只剩一个可以剩很多 这就是让cur的next指向剩下的链表第一个节点就行 因为剩下的链表他们也是顺着连着的 这就是把剩下的这部分拼接到dummy上就行

cur -> next = (l1 != NULL ? l1 : l2); 

###到这一部分就是只剩一个哦

不对的，不是只剩下一个，当到这一步时是说明有一个链表已经读取完毕，剩下一个链表可以是一个也可以是多个将cur移到剩余的那个非空链表继续读入是你这条代码的真正含义。y总这道题比较特殊只剩下一个，但代码的含义是可以多个的。

好的,如果是归并排序,
mid = (l + r ) >> 1 ...... while(i < mid) ... while(j < r ) 的时候,最后是剩一个还是一段呢?

这一块的思想是一样的，其实就是将两个数组归并成一个有序的，不妨用极限思想来看，i<=mid中的所有q[i]全部小于q[mid+1]也就是j数组的第一项，那么必定小于j数组中的所有项，则先将i数组中的值全部放入临时数组k中之后再放入j数组中的值。那么当i数组全部存放完毕之后留下来的j数组可以说是完整的，当然属于一段。如果有题目中出现j数组或者i数组中只剩下最后一个那么完全是输入的值比较巧合。

懂了懂了, 感谢

#### 后面可以是一段可以是一个 我已经理解了 就是还有一个问题
i<=mid中的所有q[i]全部小于q[mid+1]也就是j数组的第一项，那么必定小于j数组中的所有项
##### i<=mid中的所有q[i]全部小于q[mid+1] 应该是已经合并完了才符合吧 比如 [1,5,6,7],[2,3,4] 要通过

if (q[i] <= q[j])    tmp[k++] = q[i++];
    else    tmp[k++] = q[j++];

##### 一一比较放入tmp，最后[5,6,7]一段都被放入tmp 但是这之前是并不符合 所有q[i] < q[mid+1]

更多的细节我没怎么仔细去钻那可能那种极限是不成立的主要是这种思想，可以不止一个。那个极限更多的是一个比方，比较好理解。

好的，非常感谢

对，他就是一个地址，虽然地址后面通过指针还连着好多元素，但是只需要找到这个结点的地址其他的结点都在这个结点后面连着

我建议呆点ListNode *dummy = new ListNode(0);最好是用局部变量，new的话明显内存泄漏了，用智能指针的话又过于麻烦了

大佬都是怎么想到这些方法的啊，我 每次看见算法题咋都没思路，懵逼了一样

这是一个经典算法呀。比较推荐先系统学习一遍各种算法，毕竟学习一个现成的算法，比自己凭空创造一个算法简单多了hh

好的，谢谢大佬，我一边看数据结构一边在写这个

二路归并的内容在归并排序里，可以先看一下。

推荐算法基础课 常用算法都囊括了 y总讲的很细致 评论区也都是人才

有一些理解，是不是，从两个链表都从头开始比较（或者说遍历），然后挑出来一个小的就把它装到新的链表中，然后这个新的链表往下走一个，同时那个小的链表也往下走一个（因为已经找出来两个链表的两个数中较小的一个数）。再进行第二轮的比较。直到其中一个链表走完，然后从新的链表的头结点进行返回。
哈哈，写完发现也就是翻译了一下，不过清楚了些。

为什么我这个代码报 Segmentation Fault 的错误呀能不能来个大哥说一说我哪里出了问题呀
struct ListNode merge(struct ListNode l1, struct ListNode l2) {
struct ListNode p1,p2,p3,*du=l1;
p1=l1->next;
p2=l2->next;
p3=l1;
while(p1&&p2)
{
if(p1->val<=p2->val)
{
p3->next=p1;
p3=p1;
p1=p1->next;
}
else
{
p3->next=p2;
p3=p2;
p2=p2->next;

    }
}
p3->next=(p1)?p1:p2;
return l1;

}

y总是神

来个一行的解法

return !l1?l2:(!l2?l1:(l1->val<l2->val?(l1->next=merge(l1->next,l2),l1):(l2->next=merge(l1,l2->next),l2)));

cur -> next = (l1 != NULL ? l1 : l2);这个什么意思大佬们

这道题递归的时间复杂度是多少啊各位大佬？有没有什么复杂度讲解的传送门！！！万分感谢

y总，这里new了以后为啥不用delete呢，什么时候delete我有点迷

你都delete了还怎么传dummy的下一个节点回去？？？

但是我删了以后也能ac

你的意思是你的代码是
delete dummy;
return dummy->next;

对

由于看不到底层执行代码我也不清楚了，delete就是释放指针指向的内存空间。但是该指针依旧是继续存在的。如果不delete就会造成内存泄漏

所以
delete dummy;
return dummy->next;
这样写是对的吗

umm我反应过来了，这么写是对的，因为delete dummy以后，dummy指向这块内存空间就没有了，但是 这个dummy指针还是会存在，因此用它来访问next是可以的。

y总就是y总，代码太简洁了，学到了学到了

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

            }
            else{  //为什么用if(l1->val>=l2->val)出现Segmentation Fault ， 这两个有什么区别？
                l3->next=l2;       
                l2=l2->next;

            }
            l3=l3->next;
             }l3->next= (l1!=NULL?l1:l2);
            return head->next;

    }
};

我试了啊，改成>=没有段错误

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

            }
            else{  //为什么用if(l1->val>=l2->val)出现Segmentation Fault ， 这两个有什么区别？
                l3->next=l1;       
                l1=l1->next;
            }
            l3=l3->next;
        }
        l3->next= (l1!=NULL?l1:l2);
        return head->next;
    }
};

想问一下为什么只需要返回头节点就可以了啊

同问

因为链表都是连在一起的啊，传一个头节点，后面的节点不都知道了吗