mpweixin用户普通 2024年5月14日上午11:55

打卡成功！！

0 赞同 0 条回复

刘成志永久会员 2023年10月8日下午10:37

/**
* 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 trainningPlan(ListNode* l1, ListNode* l2) {
if(l1 nullptr)
{
return l2;
}
else if(l2 nullptr)
{
return l1;
}
else if(l1->val < l2->val)
{
l1->next = trainningPlan(l1->next, l2);
return l1;
}
else
{
l2->next = trainningPlan(l1, l2->next);
return l2;
}
}
};
递归退出条件为其中一个链表指向末尾，未指向末尾时比较节点的值，然后merge 指向小的值。
时间和空间复杂度为O(m+n)

0 赞同 0 条回复

慎言永久会员 2023年8月31日下午10:33

###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* pre=new ListNode(-1);
    ListNode* cur=pre;
    while (l1 != NULL && l2 != NULL)
    {    if (l1->val <= l2->val) 
        {
            cur->next=l1;
            l1=l1->next;
        }
        else{
            cur->next=l2;
            l2=l2->next;
        }
        cur=cur->next;
    }
    cur->next = l1 == NULL ? l2 : l1;
    return pre->next;
}

};

0 赞同 0 条回复

mpweixin用户普通 2023年8月23日上午11:06

1.初始化：dum，cur指向dum
2.循环合并：
whlie l1 and l2:
if l1.val < l2.val:
cur.next, l1 = l1, l1.next
else:
cur.next, l2 = l2, l2.next
cur = cur.next
3.合并尾部节点：cur.next = l1 if l1else l2
4.返回值：dum.next

0 赞同 0 条回复

我一定要坚持打卡普通 2023年8月22日下午9:14

> Problem: 21. 合并两个有序链表

思路

讲述看到这一题的思路

先判定两个给如的头节点是否为空，若有一个为空，则返回另一个头结点即可
如果两个都不为空，则用两个指针分别指向两个链表，并构建一个新的带头结点的链表，头结点置值为0，用temp指针指向头结点的下一个，temp指向新插入节点要插入的位置，在返回的时候，返回头结点的next即可。然后用两个指针两个链表开始遍历，找两个指针指向的节点值较小的一个并插入到新链表中，同时让该指针后移并让temp后移指向新插入节点的位置，不断遍历直至两个指针有一个为空

如果有一个为空，则表明改链表已经遍历完成，则将另一个链表中剩余的元素插入到新链表后边即可，这里不要忘记做一次判定

解题方法

描述你的解题方法

这里代码实现没有用到递归，直接用的两个链表遍历

先判断头结点，在做进一步数据处理

创建一个新的链表并设定头结点，然后返回头结点的next为结果链表

在判定两个链表哪个空的时候，使用三目运算符，比较快捷

找两个链表指针中比较小的值并进行新链表插入

复杂度

时间复杂度:

$O(n+m)$

m 和 n 分别是链表的长度

空间复杂度:

$O(1)$

Code

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode p1= list1;
        ListNode p2= list2;

        if (p1==null||p2==null) {// 两个链表中任意一个是空 则返回另一个链表的头结点
            if (p1==null) {
                return p2;
            }
            return p1;
        }
//     下边是两个链表都不为空的情况
//      先找到两个链表中当前指针指向的较小的值，然后将其插入到新链表中，并将指针后移并不断重复，
//      直到一个链表为空，然后将非空链表接到新链表尾部
        ListNode list = new ListNode(0);// 新链表设定头结点，返回时返回头结点后边的一个节点
        ListNode tempListNode =list;
//      这里先将一个链表遍历完，并向新链表中进行插入数据
        while ((p1!= null)&&(p2 != null)) {         
            if (p1.val<=p2.val) {// 找两个指针指向的节点中较小的值
                tempListNode.next = p1;
                tempListNode=tempListNode.next;
                p1=p1.next;
            }else {
                tempListNode.next = p2;
                tempListNode=tempListNode.next;
                p2=p2.next;
            }
        }
        //上边代码执行完 p1  和 p2 一定有一个是空的
        tempListNode.next = p1== null ? p2 : p1;// 三目运算符 直接获得值



//      if (p1==null) {//说明p1 执行遍历完，需要将p2剩余的数据插入到新俩表后边
//          tempListNode.next=p2;   
//      }else {
//          tempListNode.next=p1;   
//      }


        return list.next;

    }
}

   此处进行复制

1 赞同 0 条回复

梧葳普通 2023年8月22日下午8:53

// 创建新的链表，将原有两个链表按递增顺序串起来
“””
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
// 判空
if (l1 NULL && l2 NULL) {
return NULL;
}
// 遍历
struct ListNode head;
struct ListNode* tmp_head = &head;
while (l1 != NULL && l2 != NULL) {
// l1结点与l2结点比较
if (l1->val <= l2->val) {
tmp_head->next = l1;
l1 = l1->next;
} else {
tmp_head->next = l2;
l2 = l2->next;
}
tmp_head = tmp_head->next;
}

//最后判断尾结点
tmp_head->next = (l1 == NULL ? l2 : l1);

// 返回
return head.next;

}
“””

0 赞同 0 条回复

黎明之前普通 2023年8月22日下午12:42

//创建一个空链表有个辅助节点为空节点，储存合并组成链表
//循环l1 和l2链表将小值存入temp中如果两个链表中有一个为空，则要将另外一个的链表的最后一个值传给temp
ListNode merge = new ListNode(0);
ListNode temp = merge;
while(l1!=NULL&&l2!= NULL)
{
if(l1.val<l2.val)
{
temp.next = l1;
l1 = l1.next;
}
else{
temp.next = l2;
l2= l2.next;

}
temp = temp.next;

}
temp.next = l1NULL?l2:l1;
return merge.next;

0 赞同 0 条回复

Serena 普通 2023年8月19日下午3:31

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //创建一个空节点，储存合并后的链表
        ListNode merge=new ListNode(0);
        ListNode temp=merge;

        //比较数的大小，将较小数加到merge后
        while(l1!=null && l2!=null){
            if(l1.val < l2.val){
                temp.next=l1;
                l1=l1.next;
            }else{
                temp.next=l2;
                l2=l2.next;
            }
            temp=temp.next;
        }

        //将两个莲表示剩余的部分加到merge里
        temp.next= l1==null?l2:l1;
        return merge. Next;
    }
}

0 赞同 0 条回复

Di questa storia sempre a lie to 普通 2023年8月18日下午3:22

//定义一个新链表存放合并后的链表
//链表元素比较，将小的值存放到新链表
//若l1或l2为空链表时，直接返回非空的链表、
/**
* 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* head = new ListNode(-1);
ListNode* cur = head;
while(l1 &&l2)
{
if(l1->val >l2->val)
{
cur->next = l1;
cur = cur->next;
l1 = l1->next;
}
else
{
cur->next = l2;
cur = cur->next;
l2 = l2->next;
}
}
if(l1) cur->next = l1;
if(l2) cur->next = l2;

          return head->next;

}
};

时间复杂度： O(N+M)
空间复杂度： O(1)

0 赞同 0 条回复

海浪漂哇漂普通 2023年8月16日下午8:10

打卡
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 null){
return l2;
}
if(l2 null){
return l1;
}
ListNode newHead = new ListNode(0);
ListNode resNode = newHead;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
newHead.next = l1;
l1 = l1.next;
}else{
newHead.next = l2;
l2 = l2.next;
}
newHead = newHead.next;
}
while(l1 != null){
newHead.next = l1;
l1 = l1.next;
newHead = newHead.next;
}
while(l2 != null){
newHead.next = l2;
l2 = l2.next;
newHead = newHead.next;
}
return resNode.next;
}
}

0 赞同 0 条回复

mpweixin用户普通 2023年8月16日下午7:01

//新建一个链表用于存放俩个链表的合并；
//对每个节点都进行对比，将小的节点接入新链表里；
//时间复杂度为o(m+n);
//空间复杂度为o(1);
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1NULL)return l2;
if(l2NULL)return l1;
ListNode *l3=new ListNode(0);
ListNode *p=l3;

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

        p->next=l1==NULL?l2:l1;
         return l3->next;
    }

};

0 赞同 0 条回复

谁仁普通 2023年8月16日下午5:37

struct node * mergeSortLinklist(struct node *List1,struct node *List2)
{
//查看两个链表是否为空链表
if(List1 NULL)
{
return List1;
}
if(List2 NULL)
{
return List2;
}

//创建一个链表进行衔接，用递归方法进行回调链接直到链表为空
struct node * head;
if(List1->val < List2->val)
{
    head = List1;
    head->next = mergeSortLinklist(List1->next,List2);
}
else
{
    head = List2;
    head->next = mergeSortLinklist(List1,List2->next);
}
return head;

}
//时间复杂度为O(nlogn)，空间复杂度为O(logn)

0 赞同 0 条回复

Miracle· 普通 2023年8月15日下午10:25

时间复杂度：o(n+m),空间复杂度：o(m+n)
思路，同时遍历两个链表，将值更小的插入到新链表中，直到其中一个链表遍历完，将另一个链表插入到新链表尾部
/**
* 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 *prehead = new ListNode(-1);
ListNode *pre = prehead;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
pre->next = l1;
l1 = l1->next;
} else {
pre->next = l2;
l2 = l2->next;
}
pre = pre->next;
}
pre->next = l1 nullptr ? l2 : l1;
return prehead->next;
}
};

0 赞同 0 条回复

Delete隐身普通 2023年8月15日下午9:34

思路：同时遍历两个链表，小的节点放到新链表的尾部，直到其中一个链表遍历完，将另一个链表插入到新链表尾部
时间复杂度：O(n+m)，空间复杂度：O(1)
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode cur = head;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
// 将另一个链表的节点插入到新链表的尾部
if(l1 != null)
cur.next = l1;
else
cur.next = l2;
return head.next;
}
}

0 赞同 0 条回复

sc_Yang 普通 2023年8月15日下午8:29

时间复杂度：o(m+n)
空间复杂度：o(1)（原地合并，调哭了o(╥﹏╥)o）

/**
 * 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==NULL){
            if(l2==NULL){
                return l1;
            }else{
                return l2;
            }
        }
        // 最终结果以headPtr作为新list
        // 不操作原指针，防止内存泄漏
        ListNode* headPtr = l1;
        ListNode* prePtr = l1;
        ListNode* l1_new = l1;
        ListNode* l2_new = l2;
        // l1和l2存在任意一个到头了，后续直接拼接就行
        while(l1_new && l2_new){
            // l1_new大于l2_new
            if(l1_new->val > l2_new->val){
                // 确定新list的首个节点位置
                if(l1_new==prePtr){
                    headPtr = l2;
                    l1_new = l2_new;
                    l2_new = l2_new->next;
                    l1_new->next = prePtr;
                    prePtr = l1_new;
                    l1_new = l1_new->next;
                }else{
                    l1_new = l2_new;
                    l2_new = l2_new->next;
                    l1_new->next = prePtr->next;
                    prePtr->next = l1_new;
                    prePtr = l1_new;
                    l1_new = l1_new->next;
                }
            }
            // l2_new大于等于l1_new
            else{
                // 第一个节点，则只挪动操作指针
                if(prePtr == l1_new){
                    // 准备进行下一轮
                    l1_new = l1_new->next;
                }
                // 不是第一个节点则两个指针都挪动
                else{
                    // 续上"新"节点
                    prePtr = l1_new;
                    l1_new = l1_new->next;
                }
            }
        }
        // 收尾剩余的部分
        if(l1_new){
            prePtr = l1_new;
        }
        else{
            prePtr->next = l2_new;
        }
        return headPtr;
    }
};

0 赞同 0 条回复

Sheng 永久会员 2023年8月15日下午6:26

时间复杂度O(m+n)空间复杂度O(m+n)
思路：双指针,重点是异常处理
”’java
//单链表合并两个有序链表
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2)
{
ListNode p1 = l1;
ListNode p2 = l2;
ListNode p = null;
if(null p1)
p = p2;
if(null p2)
p = p1;
if((null != p1 && null != p2)) {
if(p1.val <= p2.val) {
p = new ListNode(p1.val);
p1 = p1.next;
}
else {
p = new ListNode(p2.val);
p2 = p2.next;
}

        ListNode tail = p;
        while(null != p1 && null != p2) {
            if(p1.val <= p2.val) {
                tail.next = p1;
                p1 = p1.next;
            }
            else {
                tail.next = p2;
                p2 = p2.next;
            }
            tail = tail.next;
        }
        if(null != p1)
            tail.next = p1;
        if(null != p2)
            tail.next = p2;
    }

    return p;
}

}

0 赞同 0 条回复

QQiing 普通 2023年8月15日下午3:37

class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 NULL && l2 NULL){
return NULL;
}
ListNode* l = new ListNode(0);// 定义一个头结点
ListNode* temp = l;
while (l1 != NULL && l2 != NULL) {
// 取较小的节点加入新表
if (l1->val <= l2->val) {
temp->next = l1;
l1 = l1->next;
} else {
temp->next = l2;
l2 = l2->next;
}
temp = temp->next;
}
if(l1 != NULL){
temp->next = l1;
}
if(l2 != NULL){
temp->next = l2;
}
return l->next;
}
};
时间复杂度O(n)，空间复杂度O(1）

0 赞同 0 条回复

一个人的风海吹了两遍普通 2023年8月15日上午9:12

最后返回的是 .next反应了半天
这句话省事
l3.next = l1null ? l2 : l1;
时间复杂度O（m+n）
空间复杂度O（1）

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

        ListNode l3=new ListNode(0);
        ListNode l4=l3;
        while (l1!=null && l2!=null){
            if(l1.val>=l2.val){
                l3.next=l2;
                l2=l2.next;
                l3=l3.next;
            } else {
                l3.next=l1;
                l1=l1.next;
                l3=l3.next;
            }

        }
        //省事
        l3.next = l1==null ? l2 : l1;

        return  l4.next;
    }
}

0 赞同 0 条回复

💮黧大王.exe 普通 2023年8月14日下午11:08

时间复杂度O(m+n)
空间复杂度O(1)
/**
* 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* l=new ListNode(0);
ListNode* head=l;
while(l1!=NULL&&l2!=NULL){
if(l1->valval){
head->next=l1;
l1=l1->next;
}
else{
head->next=l2;
l2=l2->next;
}
head=head->next;
}
if(l1NULL) head->next=l2;
else head->next=l1;
return l->next;
}
};

0 赞同 0 条回复

行动派小彩笔普通 2023年8月14日下午10:38

 // 时间O(n+m),空间O(1)
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        else if(!l2) return l1;
        ListNode *head = new ListNode(-1);
        ListNode *cur = head;
        while(l1 && l2)
        {
            if(l1->val<l2->val)
            {
                cur->next = l1;
                l1 = l1->next;
            }
            else
            {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if(l1) cur->next = l1;
        if(l2) cur->next = l2;
        return head->next;
    }
};

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月14日下午9:59

用递归实现
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 nullptr){
return l2;
}
if(l2 nullptr){
return l1;
}
if(l1->val <= l2->val){
l1->next = mergeTwoLists(l1->next, l2);
return l1;
}
else{
l2->next = mergeTwoLists(l1, l2->next);
return l2;
}
}

0 赞同 0 条回复

只吃酸菜不吃鱼普通 2023年8月14日下午9:14

class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 null) return l2;
if(l2 null) return l1;
//先找到头结点
ListNode head = null;
if(l1.val <= l2.val){
head = l1;
l1 = l1.next;
}else{
head = l2;
l2 = l2.next;
}
//合并
ListNode cur = head;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if(l1 null){
cur.next = l2;
}else{
cur.next = l1;
}
return head;
}
}

0 赞同 0 条回复

hhhhh 普通 2023年8月14日下午5:13

过

“`cpp
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* d = new ListNode(0);
ListNode* head = d;
while(l1 != nullptr && l2 != nullptr){
if(l1->val > l2->val){
d->next = l2;
l2 = l2->next;
}else{
d->next = l1;
l1 = l1->next;
}
d = d->next;
}
if(l1 == nullptr){
d->next = l2;
}
if(l2 == nullptr){
d->next = l1;
}
return head->next;
}
};

0 赞同 0 条回复

逸兴遄飞普通 2023年8月14日上午10:16

时间复杂度：O(n+m)，其中 n 和 m 分别为两个链表的长度。
空间复杂度：O(1)，只需要存储输出的空间。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 创建缓冲链表，在这里为其赋值一个辅助节点来防止空指针的出现
        ListNode now = new ListNode(-1);
        ListNode temp = now;

        // 使用while循环赋值
        while(l1 != null && l2 != null){
            // 对合并值进行比较，将较小的数优先记录在前面
            if(l1.val < l2.val){
                temp.next = l1;
                l1 = l1.next;
            } else {
                temp.next = l2;
                l2 = l2.next;
            }

            temp = temp.next;
        }

        // 进行为链表为空判断，继承未遍历结束的链表，防止某个链表遍历不完全
        temp.next = l1 == null ? l2 : l1;

        return now.next; 
    }
}

0 赞同 0 条回复

晓宇普通 2023年8月14日上午7:42

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        :type list1: Optional[ListNode]
        :type list2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        list3  = ListNode(0)
        head1 = list1
        head2 = list2
        head3 = list3
        while(head1 and head2):
            if head1.val > head2.val:
                head3.next = head2
                head2 = head2.next
            else:
                head3.next = head1
                head1 = head1.next
            head3 = head3.next

        while (head1):
            head3.next = head1
            head1 = head1.next
            head3 = head3.next

        while (head2):
            head3.next = head2
            head2 = head2.next
            head3 = head3.next

        return list3.next

本题是主要是理清楚三个指针之间的关系，并且理清楚头结点的关系。
需要考虑的情况：
1.最normal情况的比较下应当如何插入节点
2.当某一个节点走完的时候应当如何插入节点
3.考虑是否有其他的异常情况

0 赞同 0 条回复

天亮之前普通 2023年8月13日下午7:51

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode merge = new ListNode(0);
ListNode temp = merge;

    while(l1 != null && l2 != null){
        if(l1.val < l2.val){
            temp.next = l1;
            l1 = l1.next;
        }else{
            temp.next = l2;
            l2 = l2.next;
        }
        temp = temp.next;
    }
    temp.next = l1 == null ? l2 : l1;
    return merge.next;
}

}
时间复杂度为 O(n)

0 赞同 0 条回复

漂洋过海去见你永久会员 2023年8月13日下午6:22

#python解题思路：1、先判断l1和l2哪个是None，存在none就不合并直接返回另一个；2、先生成一个head头节点，用cur指向head，用cur.next来指向l1和l2比较小的那一个，谁小谁就移动指针；3、最后判断是否存在链表不为空的，直接将剩下的指向cur.next；4、返回head.next
#时间复杂度：O(n+m)，n 和 m 表示两个链表长度
#空间复杂度：O(1)
class Solution(object):
def mergeTwoLists(self, l1, l2):
“””
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
“””
if l1 is None:
return l2
elif l2 is None:
return l1

    head = ListNode(0)
    cur = head 
    while l1 and l2:
        if l1.val < l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next

    cur.next = l1 if l1 else l2

    return head.next

0 赞同 0 条回复

sincere 普通 2023年8月13日下午5:25

思路：1、遍历，小的就跟在虚拟节点后面，直到有一个遍历完；2、递归，只管当前的节点，谁小就将谁的next和另一个链表节点比较，后续状态交由子函数去判断
复杂度：1、时间复杂度O(m+n)，空间复杂度O(1)；2、时间复杂度O(m+n)，空间复杂度O(m+n)

// 遍历
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode dummy = new ListNode(-1);
        ListNode pre = dummy;

        while(l1 != null && l2 != null){
            if(l1.val > l2.val){
                pre.next = l2;
                l2 = l2.next;
            }else{
                pre.next = l1;
                l1 = l1.next;
            }
            pre = pre.next;
        }
        pre.next = (l1 == null) ? l2 : l1;

        return dummy.next;
    }
}

// 递归
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        if(l1.val>l2.val){
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }else{
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
    }
}

0 赞同 0 条回复

辰北、普通 2023年8月13日下午3:24

//递归，创建temp，合并l1，l2；首先判断链表是否为空，输出另一个；其次判断l1，l2->val大小。temp=小的，递归：temp——next= M（小的—》next，大的不变）
//时间复杂°o(N),kongjian O(n)
truct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
struct ListNode *temp=NULL;
if(!l1)
return l2;
if(!l2)
return l1;
if(l1->valval){
temp=l1;
temp->next=mergeTwoLists(l1->next,l2);
}else{
temp=l2;
temp->next=mergeTwoLists(l1,l2->next);
}
return temp;

}

0 赞同 0 条回复

天亮说晚安普通 2023年8月13日下午1:14

思路：每次取两个链表较小的值，最后取某个链表剩下的值
时间复杂度O(n)，空间复杂度O(n)

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode resList = new ListNode();
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode p3 = resList;
        while(p1!=null && p2!=null){
            ListNode t = new ListNode();
            if(p1.val>p2.val){
                t.val = p2.val;
                p3.next = t;
                p3 = p3.next;
                p2 = p2.next;
            }else{
                t.val = p1.val;
                p3.next = t;
                p3 = p3.next;
                p1 = p1.next;
            }
        }
        if(p1==null){
            p3.next = p2;
        }else{
            p3.next = p1;
        }
        return resList.next;
    }
}

0 赞同 0 条回复

WA 普通 2023年8月13日上午10:54

/**
 * 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* p = new ListNode(-1);
        ListNode* t = p;
        while (l1 and l2){
            if (l1 -> val < l2 -> val){
                t -> next = l1;
                l1 = l1 -> next;
            }
            else{
                t -> next = l2;
                l2 = l2 -> next;
            }
            t = t -> next;
        }
        if (l1 != NULL) t -> next =  l1;
        else t -> next = l2;
        return p -> next;
    }
};
打卡

0 赞同 0 条回复

Jou Siankwa 普通 2023年8月13日上午10:29

如果链表元素小，就一直将该链表元素加入新链表，一个链表到达末尾，再把领一个链表从指针位置开始全部加入新链表。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode nodeA = l1, nodeB = l2;
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(l1 != null && l2 != null){
            while(l1 != null && l2 != null && l1.val <= l2.val){
                cur.next = new ListNode(l1.val);
                cur = cur.next;
                l1 = l1.next;
            }
            while(l1 != null && l2 != null && l1.val > l2.val){
                cur.next = new ListNode(l2.val);
                cur = cur.next;
                l2 = l2.next;
            }

        }
        while (l1 != null){
            cur.next = new ListNode(l1.val);
            cur = cur.next;
            l1 = l1.next;
        }
        while(l2 != null){
            cur.next = new ListNode(l2.val);
            cur = cur.next;
            l2 = l2.next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(1);
        ListNode l12 = new ListNode(2);
        ListNode l13 = new ListNode(4);

        ListNode l2 = new ListNode(1);
        ListNode l22 = new ListNode(3);
        ListNode l23 = new ListNode(4);

        l1.next = l12;
        l12.next = l13;
        l2.next = l22;
        l22.next = l23;

        Solution sol = new Solution();
        ListNode listNode = sol.mergeTwoLists(l1, l2);
        while(listNode != null){
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年8月13日上午3:33

時間複雜度: O(N+M), 空間複雜度 O(1)
利用一個 dummy node 來當起點, 依序比較兩個鏈表的元素大小並依序接上
最後注意要判斷如果有剩下沒接上的元素要記得接上去


class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);;
        
        ListNode* temp_1 = l1;
        ListNode* temp_2 = l2;
        ListNode* current = dummy;
        while (temp_1 != NULL && temp_2 != NULL) {
            if (temp_1->val >= temp_2->val) {
                current->next = temp_2;
                temp_2 = temp_2->next;
            }
            else if (temp_1->val < temp_2->val) {
                current->next = temp_1;
                temp_1 = temp_1->next;
            }
            current = current->next;
        }

        if (temp_1) {
            current->next = temp_1;
        }

        if (temp_2) {
            current->next = temp_2;
        }

        return dummy->next;
    }
};

        return dummy->next;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年8月13日上午1:36

时间复杂度：O(N+M), 空间复杂度O(N+M)
递归的思想，递归最后对比的一定是一个空和值对比，返回值

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        if(l1.val>l2.val){
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }else{
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
    }
}

0 赞同 0 条回复

Marc 普通 2023年8月13日上午1:19

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        dump = ListNode(-1)
        cur = dump 
        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1 
                l1 = l1.next 
            else:
                cur.next = l2
                l2 = l2.next  
            cur = cur.next 
        if l1:
            cur.next = l1 
        else:
            cur.next = l2 
        return dump.next

时间O(m + n ) 空间 o1

0 赞同 0 条回复

clown 普通 2023年8月13日上午12:46

时间复杂度O(m+n)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode p = l1;
ListNode q = l2;
ListNode head = new ListNode(0);
ListNode cur = head;
while(p != null && q != null){
if(q.val < p.val){
cur.next = q;
q = q.next;
} else {
cur.next = p;
p = p.next;
}
cur = cur.next;
}
if(p != null){
cur.next = p;
}
if(q != null){
cur.next = q;
}
return head.next;
}

0 赞同 0 条回复

Prime 普通 2023年8月12日下午11:58

时间复杂度O(n+m),空间复杂度O(1)

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        dummy = ListNode(0)
        cur = dummy

        while l1 and l2:
            if l1.val < l2.val:
                cur.next = l1
                l1 = l1.next
            else:
                cur.next = l2
                l2 = l2.next
            cur = cur.next

        if l1:
            cur.next = l1
        if l2:
            cur.next = l2

        return dummy.next

0 赞同 0 条回复

木子有点甜🍒 普通 2023年8月12日下午11:37

“`python
构建了pre，cur两个节点，这两个节点作为新链表构建用。
pre始终指向该链表的第一个节点，cur则跟随l1,l2遍历情况变动：
当l1的节点值更小时，cur就将新链表的下一个节点指向l1当前节点，此时l2暂停遍历，l1继续向下；反之亦然。

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
cur = ListNode(-1)
pre = cur

    if l1 is None: return l2
    if l2 is None: return l1

    while l1 and l2:
        if l1.val<=l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next

        cur = cur.next

        if l1:
            cur.next = l1
        else:
            cur.next = l2


    return pre.next

0 赞同 0 条回复

mpweixin用户普通 2023年8月12日下午11:05

打卡

/**
 * 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* merge = new ListNode(0);//新new一个节点 避免空指针
        ListNode * temp = merge;
        while(l1 != NULL && l2 != NULL){
            if(l1->val <= l2->val){
                temp->next = l1;
                l1 = l1->next;
            }else{
                temp->next = l2;
                l2 = l2->next;
            }
            temp = temp->next;//temp节点也要往后移才行 
        }
        temp->next = l1 ? l1 : l2;
        return merge->next;
    }
};

0 赞同 0 条回复

JustRtn 普通 2023年8月12日下午10:48

时间复杂度O(m+n),空间复杂度O(1)

“`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) {
if (l1 == nullptr) {
return l2;
}
if (l2 == nullptr) {
return l1;
}
ListNode *p { nullptr };
if (l1->val < l2->val) {
p = l1;
l1 = l1->next;
} else {
p = l2;
l2 = l2->next;
}
auto *head = p;
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
p->next = l1;
l1 = l1->next;
} else {
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
if (l1 != nullptr) {
p->next = l1;
} else if (l2 != nullptr) {
p->next = l2;
}
return head;
}
};
“`

0 赞同 0 条回复

. 永久会员 2023年8月12日下午10:25

class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//这个感觉递归也挺简单。
if(l1 null) return l2;
if(l2 null) return l1;
if(l1.val <= l2.val){
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}
else{
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}
}
}

0 赞同 0 条回复

Scanner 永久会员 2023年8月12日下午10:18

/**
* 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* l3 = new ListNode(0);
ListNode* p = l3; //p负责构建新链表

    while(l1 != NULL && l2 != NULL) { //当两组链表都没遍历完时
        if(l1->val > l2->val) p->next = l2, l2 = l2->next;
        else p->next = l1, l1 = l1->next;
        p = p->next;
    }

    //当两组链表其中一条没遍历完时
    while(l1 != NULL) p->next = l1, l1 = l1->next, p = p->next; //勿忘让p向后移动
    while(l2 != NULL) p->next = l2, l2 = l2->next, p = p->next;

    return l3->next;
}

};

0 赞同 0 条回复

mpweixin用户普通 2023年8月12日下午9:56

时间复杂度O(m+n) 空间复杂度O(1)

/**
 * 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* h = new ListNode();
        ListNode* hh = h;

        while(l1 != NULL && l2 != NULL) {
            if(l1->val < l2->val) {
                hh->next = l1;
                l1 = l1->next;
            }
            else {
                hh->next = l2;
                l2 = l2->next;
            }
            hh = hh->next;
        }
        hh->next = l1 == NULL? l2:l1;
        return h->next;

    }
};

0 赞同 0 条回复

别扒拉我普通 2023年8月12日下午9:52

1、迭代
2、时间复杂度O(n+m)，空间复杂度O(1)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null && l2 == null){
            return null;
        }
        ListNode res = new ListNode(-1);
        ListNode node = res;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                node.next = l1; 
                l1 = l1.next;
            }else{
                node.next = l2;
                l2 = l2.next;
            }
            node = node.next;
        }
        if(l1 != null)  node.next = l1;
        if(l2 != null)  node.next = l2;
        return res.next;
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年8月12日下午9:44

两个指针逐个比大小即可，谁小谁进入链表，然后往后跳一步，如此循环直至某个指针为空，此时将新链表尾节点的next指向另一个不为空的指针即可；
时间复杂度：O(n); 空间复杂度：O（1）

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }

        ListNode p = l1, q = l2;
        ListNode head = new ListNode(-1);
        ListNode temp = head;
        while (p != null && q != null) {
            if (p.val <= q.val) {
                temp.next = p;
                temp = p;
                p = p.next;
            } else {
                temp.next = q;
                temp = q;
                q = q.next;
            }
        }
        if (p != null) {
            temp.next = p;
        }
        if ( q != null) {
            temp.next = q;
        }
        return head.next;
    }
}

0 赞同 0 条回复

小肸永久会员 2023年8月12日下午9:27

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode cur = dummyHead;
        //这里while判断条件写一个函数
        while (l1 != null && l2 != null) {
            //如果是多个有序链表，这里可以写一个函数返回一个下一个节点
            ListNode tmp = (l1.val > l2.val ? l2 : l1);
            cur.next = tmp;
            //这里写一个函数找到需要移动的节点
            if (tmp == l1) {
                l1 = l1.next;
            } else {
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = (l1 == null ? l2 : l1);
        return dummyHead.next;
    }
}

0 赞同 0 条回复

Joel 普通 2023年8月12日下午9:26

时间复杂度:O(m+n) 空间复杂度：O(m+n)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 == None and l2 == None:
            return None
        elif l1 == None and l2 != None:
            return l2
        elif l1 != None and l2 == None:
            return l1
        head = ListNode()
        dummy = head
        if l1.val <= l2.val:
            head.val = l1.val
            l1 = l1.next
        else:
            head.val = l2.val
            l2 = l2.next
        while True:
            if l1 == None and l2 == None:
                return dummy
            elif l1 == None and l2 != None:
                head.next = l2
                return dummy
            elif l1 != None and l2 == None:
                head.next = l1
                return dummy
            else:
                node = ListNode()
                head.next = node
                if l1.val <= l2.val:
                    node.val = l1.val
                    l1 = l1.next
                else:
                    node.val = l2.val
                    l2 = l2.next
                head = head.next

0 赞同 0 条回复

c 普通 2023年8月12日下午9:10

时间O(m+n)空间O(1)

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

0 赞同 0 条回复

【链表专题】剑指 Offer 25. 合并两个排序的链表

共以下 48 个回答

思路

解题方法

复杂度

时间复杂度:

空间复杂度:

Code

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

# 回答此问题取消回复

【链表专题】剑指 Offer 25. 合并两个排序的链表

共以下 48 个回答

思路

解题方法

复杂度

时间复杂度:

空间复杂度:

Code

Definition for singly-linked list.

class ListNode:

def init(self, x):

self.val = x

self.next = None

# 回答此问题 取消回复

# 回答此问题取消回复