【链表专题】剑指 Offer 25. 合并两个排序的链表-跟着帅地玩副业，开拓第二曲线PlayOffer

lucca 普通 2022年12月30日上午1:05

堆排序写法

/**
 * 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();
        ListNode p = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                p.next = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }


        if (l1 != null) p.next = l1;
        if (l2 != null) p.next = l2;
        return head.next;
    }

}

0 赞同 0 条回复

糖鑫普通 2022年12月1日下午10:07

/**
 * 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;
        ListNode insert;
        if(l1==null){//特例处理
            return l2;
        }else if(l2==null){
            return l1;
        }else if(l1.val<l2.val){//确定头节点
            head=l1;
            insert=l2;
        }else{
            head=l2;
            insert=l1;
        }
        ListNode cur=head;
        ListNode node;
        //遍历基础链表，寻找插入位置，将节点依次插入
        while(cur.next!=null&&insert!=null){//cur.next!=null后续判断用到cur.next.val为了不报错
            //寻找插入位置
            if(insert.val<=cur.next.val && insert.val>=cur.val){
                node=insert.next;//!
                insert.next=cur.next;
                cur.next=insert;
                insert=node;//依次插入
            }
            cur=cur.next;
        }
        if(insert!=null){//特例处理
            cur.next=insert;
        }
        return head;
    }
}

0 赞同 0 条回复

格格巫普通 2022年11月19日下午4:11

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let dummy = new ListNode(0);
    let cur = dummy;
    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;
    }else{
        cur.next = l2;
    }

    return dummy.next;

};

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

0 赞同 0 条回复

mpweixin用户普通 2022年11月17日下午10:09

class Solution:
    def Merge(self , pHead1: ListNode, pHead2: ListNode) -> ListNode:
        # 特殊情况，空链表+非空 == 直接是非空链表
        # 比较较小的值
        if pHead1 == None:
            return pHead2
        if pHead2 == None:
            return pHead1
        # 比较第一个较小值
        if pHead1.val <= pHead2.val:
            pHead1.next = self.Merge(pHead1.next, pHead2)
            return pHead1
        else:
            pHead2.next = self.Merge(pHead1, pHead2.next)
            return pHead2

0 赞同 0 条回复

PatNick 普通 2022年11月13日上午11:35

def next_node(first,second,cur):
    '''
    对比两个指针当前所在节点的大小：小的节点加入到新链中，并向后移动指针
    Args:
        first:
        second:
        cur:新链到当前节点

    Returns:

    '''
    if first.val <= second.val:
        cur.next = first
        cur = cur.next
        first = first.next
    else:
        cur.next = second
        cur = cur.next
        second = second.next
    return first,second,cur


def mergeTwoList(l1:ListNode,l2:ListNode)->ListNode:
    # 如果l1或l2不存在返回另一个
    if not l1:
        return l2
    if not l2:
        return l1

    if not l1 and not l2:
        return None

    first = l1
    second = l2
    head = None
    # 确定新链到头节点
    if first.val <= second.val:
        head = first
        first = first.next
    else:
        head = second
        second = second.next

    cur = head

    # 只要两个指针没有走到链条到终点，就一直将较小到放入新链
    while first and second:
        first,second,cur = next_node(first,second,cur)

    # 当一个链中所有节点都加入到新链后，另一个链就将剩下到节点一下加入新链
    # if first:
    #     cur.next= first
    #
    # if second:
    #     cur.next = second
    # 换成三目运算
    cur.next = first if first else second

    return head

0 赞同 0 条回复

叶页耶夜烨邺普通 2022年10月28日下午6:06

归并思想

/**
 * 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* dummy = new ListNode(-1);
        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* res = dummy->next;
        delete dummy;
        return res;
    }
};

0 赞同 0 条回复

和普通 2022年10月27日下午2:51

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //新建一个虚拟头结点
        ListNode head=new ListNode(-1);
        ListNode p=head;
       while(l1!=null&&l2!=null){
           if (l1.val< l2.val){
               p.next=l1;
               l1=l1.next;
           }else{
               p.next=l2;
               l2=l2.next;
           }
           p=p.next;//更换头结点
       }if (l1==null){
           p.next=l2;//如果l1遍历结束，就可以直接将剩下的l2放入，下同。
        }else if (l2==null){
           p.next=l1;
        }
        return head.next;
     }

0 赞同 0 条回复

。。。。普通 2022年10月27日下午2:47

代码如下

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode <em>next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode</em> mergeTwoLists(ListNode* l1, ListNode* l2) {
                if(l1<span class="text-highlighted-inline" style="background-color: #fffd38;">nullptr) return l2;
                if(l2</span>nullptr) return l1;
                ListNode* merge =new ListNode(0);
                ListNode* cur=merge;
                while(l1!=nullptr&&l2!=nullptr)<br />
    {                 if(l1->val<l2->val)   {
                    cur->next=l1;
                    l1=l1->next;
                    }
                else{
                    cur->next=l2;
                    l2=l2->next;
                                }
                                cur=cur->next;
                                }
                if(l1!=nullptr) cur->next=l1;
                if(l2!=nullptr) cur->next=l2;
                return merge->next;
    }
};

0 赞同 0 条回复

彭靖永久会员 2022年10月26日下午5:13

/**
 * 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;
        ListNode* temp;
        l3=new ListNode;
        temp=l3;
        while(l1!=NULL&&l2!=NULL)
        {
            if(l1->val<=l2->val)
            {
                l3->next=l1;
                l1=l1->next;           
            }
            else
            {
                l3->next=l2;
                l2=l2->next;
            }
            l3=l3->next;
        }

        if(l1==NULL)
        {
            l3->next=l2;
        }
        if(l2==NULL)
        {
            l3->next=l1;
        }


        return temp->next;
    }
};
新手努力中

0 赞同 0 条回复

Xiao 普通 2022年10月25日下午9:33

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
         if(l1 == null || l2 == null)
            return l1 == null ? l2 : 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 条回复

努力刷题普通 2022年10月25日上午7:13

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = cur = ListNode(-1)
        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 dummy.next
时间复杂度O(m+n)
空间复杂度O(1)

0 赞同 0 条回复

小趴菜永久会员 2022年10月25日上午1:19

时间o(m+n),空间o(1)
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode p = dummy;
while(l1!=null&&l2!=null){
if(l1.val>l2.val){
p.next=l2;
p=p.next;
l2=l2.next;
}
else if(l1.val<=l2.val){
p.next=l1;
p=p.next;
l1=l1.next;
}
}
//给边界情况打个补丁或者说循环跳出后的操作
if(l1!=null){
p.next=l1;
}
if(l2!=null){
p.next=l2;
}
//当然是返回哑节点后的所有部分啦
return dummy.next;
}
}

0 赞同 0 条回复

cxc 普通 2022年10月24日下午11:26

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       ListNode dummy = new ListNode(0);
       ListNode cur = dummy;

       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;
       }
       // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
       cur.next = l1 == null? l2 : l1;
       return dummy.next;
    }
}

0 赞同 0 条回复

星河普通 2022年10月24日下午9:41

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dum = new ListNode(0), cur = dum;
        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 ? l1 : l2;
        return dum.next;
    }
}
时间O(M+N)，空间O(1)

0 赞同 0 条回复

🚲南下普通 2022年10月24日上午9:51

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

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* pre = new ListNode(-1); //作为头节点固定位置
        ListNode* temp = pre; 
        while(l1!=nullptr && l2!=nullptr){
            if(l1->val < l2->val){
                temp->next = l1;//更新temp的next
                l1 = l1->next;
            }else{
                temp->next = l2;
                l2 = l2->next;
            }
            temp = temp->next; //同时移动到最新位置
        }
        temp->next = l1==nullptr?l2:l1;

        return pre->next;

    }
};

0 赞同 0 条回复

啊哈普通 2022年10月24日上午12:08

/**
 * 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(0);
        ListNode* q = p;
        //相同长度合并。归入p中
        while(l1 != NULL && l2 != NULL){
            if(l1->val < l2->val)
            {
                q -> next = l1;
                l1 = l1-> next;
            }
            else{
                q-> next = l2;
                l2 = l2->next;
            }
            //重要
            q = q->next;
        }
        q -> next = (l1 == NULL) ? l2 : l1;

        return p->next;
    }
};

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

0 赞同 0 条回复

阿白普通 2022年10月23日下午11:10

1、构造一个空节点temp，当两个输入节点均不为nullptr时，可比较，temp指向的下一节点为值较小的那个，temp++，同时那个节点也++
2、当有一个输入节点为nullptr时，temp下一节点为另一个输入节点。
3、时间复杂度O（n），空间复杂度O（n）

class ListNode
{
public:
    ListNode(){};
    ListNode(int m):val(m),next(nullptr){};
    ListNode* mergeTwoLists(ListNode* fisrt, ListNode *second);

    ~ListNode();

private:
    int val;
    ListNode* next;
};

ListNode* ListNode::mergeTwoLists(ListNode* fisrt, ListNode *second)
{
    ListNode *merge = new ListNode(0);
    ListNode *temp = merge;

    while (fisrt != nullptr && second != nullptr)
    {
        if (fisrt->val < second->val)
        {
            temp->next = fisrt;
            fisrt = fisrt->next;
        }
        else
        {
            temp->next = second;
            second = second->next;
        }
        temp = temp->next;
    }
    temp->next = fisrt == nullptr ? second : fisrt;

    return merge->next;
}

0 赞同 0 条回复

symbol 普通 2022年10月23日下午9:06

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil{//递归终止条件
        return l2
    }
    if l2 == nil{//递归终止条件
        return l1
    }
    if l1.Val > l2.Val{ //交换l1和l2
        l2,l1 = l1, l2
    }
    l1.Next = mergeTwoLists(l1.Next, l2)
    return l1
}

0 赞同 0 条回复

Ruby🗽 普通 2022年10月23日下午6:02

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode merge = new ListNode(0);
        ListNode temp = merge;
        while (list1 != null && list2 != null){
            if ( list1.val <= list2.val ){
                temp.next = list1;
                list1 = list1.next;
            }else {
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        temp.next = list1 == null ? list2 : list1;
        return merge.next;
    }
}

时间复杂度 n+m
空间复杂度 1

0 赞同 0 条回复

Gg 普通 2022年10月23日下午5:49

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        ListNode p1 = l1;
        ListNode p2 = l2;
        // 遍历两链表，取val小节点，p移动到该节点
        while(p1 != null && p2 != null){
            if(p1.val < p2.val){
                p.next = p1;
                p1 = p1.next;
            }else{
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        p.next = p1 == null ? p2:p1;
        return dummy.next;
    }
}

0 赞同 0 条回复

just 普通 2022年10月23日下午4:26

//典型的双指针

class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy=new ListNode(0,nullptr);
ListNode* a=l1, * b=l2,* pre=dummy;
while(a && b){
if(a->valval){
pre->next=a;
a=a->next;
}
else{
pre->next=b;
b=b->next;
}
pre=pre->next;
pre->next=nullptr;
}
if(a) pre->next=a;
if(b) pre->next=b;
return dummy->next;

};

0 赞同 0 条回复

刺猬普通 2022年10月23日下午4:24

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode;
        ListNode* l3 = head;
        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;
    }
};

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

0 赞同 0 条回复

YZ 普通 2022年10月23日下午1:17

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //看见这个题，第一反应就是归并排序，二路归并，不过链表的知识掌握的不足(不会创建一个空链表存放比较后的结点)
        //和数组不同的是，归并时不能只赋值链表的val值，而是要把整个结点连接
        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;   //注意这里是头结点的下一个，而不是指针temp的下一个，因为指针temp连接了没有排完
//的链表
    }
};

刚在题解中看到递归解法，还不太理解，原理相同

0 赞同 0 条回复

云雾里普通 2022年10月23日上午11:58

/**
 * 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 shaobing =  new ListNode(-1);
      ListNode temp =shaobing;
      while(l1!=null || l2!=null){
          if(l1==null){
            temp.next=l2;
            break;
          }
          if(l2==null){
            temp.next=l1;
            break;
          }
          if(l1.val<l2.val){
              temp.next=new ListNode(l1.val);
              l1=l1.next;
          }else{
             temp.next=new ListNode(l2.val);
              l2=l2.next;
          }
        temp=temp.next;
        if(temp==null)
        {
            break;
        }
      }
      return shaobing.next;
    }
}

0 赞同 0 条回复

@ 普通 2022年10月23日上午9:59

迭代，但写的还是有的冗余了，有待优化

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode res = null;


        if(l1.val < l2.val){
            res = l1;
            l1 = l1.next;
        } else {
            res = l2;
            l2 = l2.next;
        }

        ListNode res2 =res;

        while(l1 != null || l2 != null) {
            if(l2 != null && l1 == null) {
                res.next = l2;
                res = res.next;
                l2 = l2.next;
            }

            if(l1 != null && l2 == null) {
                res.next =l1;
                res = res.next;
                l1 = l1.next;
            }


            if(l1 != null && l2 != null && l1.val <= l2.val){
                res.next =l1;
                res = res.next;
                l1 = l1.next;
            }

            if(l1 != null && l2 != null && l1.val > l2.val) {
                res.next = l2;
                res = res.next;
                l2 = l2.next;
            }


        }

        return res2;

    }


}

0 赞同 1 条回复

shuaidi 永久会员 @ @ 2022年10月23日上午10:57

当你觉得自己的代码有点冗余的时候，最好的学习方法就是看一下别人怎么写的哦，然后模仿他们优雅的写法。

登录以回复

浅夏的无奈普通 2022年10月23日上午8:42

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //创建两个辅助节点
        ListNode head = new ListNode(0),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;
        }
        //判断给出的链表是否存在空链表
        cur.next=l1!=null?l1:l2;
        //返回结果
        return head.next;

    }
}

0 赞同 0 条回复

-辰华- 永久会员 2022年10月23日上午12:11

解法一：递归

/**
 * 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) {
        // 递归
        // l1或l2链表为空，返回非空链表
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        // 比较l1与l2头节点的值大小
        if (l1.val > l2.val) {// l2小
            l2.next = mergeTwoLists(l1, l2.next);// 合并,直到l1为空结束递归
            return l2;
        } else {// l1小
           l1.next = mergeTwoLists(l1.next, l2);
           return l1;
        }
    }
}

时间复杂度：O(m+n),其中m为l1长度，n为l2长度
空间复杂度：O(m+n)
解法二:非递归

/**
 * 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 dummy = new ListNode(0), node = dummy;
        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;
        }
        node.next = l1 == null? l2: l1;
        return dummy.next;
    }
}

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

0 赞同 0 条回复

yanshuojune 普通 2022年10月22日下午11:57

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
       # 迭代
        # 创建一个初始值为0的链表
        merge = ListNode()
        pre = merge
        while l1 and l2:
            # 若l1的值不大于l2的值时，将创建的链表末尾节点指向l1，l1想后移动一位
            if l1.val <= l2.val:
                pre.next = l1
                l1 = l1.next
            # 若l1的值大于l2的值时，将创建的链表末尾节点指向l2，l2想后移动一位
            else:
                pre.next = l2
                l2 = l2.next
            pre = pre.next
        # l1或l2遍历结束后，将merge尾节点指向未遍历完成链表的剩余部分
        pre.next = l1 if l1 is not None else l2
        #返回除首节点外的链表
        return merge.next

时间复杂度：O（m+n）
空间复杂度：O（1）

0 赞同 0 条回复

mpweixin用户永久会员 2022年10月22日下午11:43

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

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

0 赞同 0 条回复

优秀市民普通 2022年10月22日下午11:28

def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        preHead = ListNode(-1)
        temp = preHead
        while l1 and l2:
            if (l1.val < l2.val):
                temp.next = l1
                l1 = l1.next
            else:
                temp.next = l2
                l2 = l2.next
            temp = temp.next
        temp.next = l1 if l1 is not None else l2
        return preHead.next

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

0 赞同 0 条回复

Tolkien 永久会员 2022年10月22日下午10:40

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

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 1. 创建一个链表存储结果
        ListNode mergeList = new ListNode(0);
        ListNode temp = mergeList;

        // 2. 若其中一个指针指向的值小于另一个，则该值加入结果链表，指针下移，直到其中一个指针为空
        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;
        }

        // 3. 判断哪个链表为空，则将另外一个链表加入结果链表
        temp.next = l1 == null ? l2 : l1;

        return mergeList.next;
    }

0 赞同 0 条回复

Magi 普通 2022年10月22日下午10:09

  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
   //这次我们要创建一个辅助结点来辅助，因为不好判断头节点下一个是否为空
        ListNode magi = new ListNode(0);
        ListNode temp = magi;

        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 magi.next;


    }

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

0 赞同 0 条回复

波波_1936 普通 2022年10月22日下午9:12

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

        ListNode preNode = new ListNode(-1);
        ListNode cu = preNode;

        while (l1 != null && l2 != null) {
            int val1 = l1.val;
            int val2 = l2.val;
            if (val1 < val2) {
                cu.next = l1;
                l1 = l1.next;
            } else {
                cu.next = l2;
                l2 = l2.next;
            }
            cu = cu.next;
        }
        if (l1 != null) {
            cu.next = l1;
        }
        if (l2 != null) {
            cu.next = l2;
        }
        return preNode.next;

    }

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

0 赞同 0 条回复

cute. 普通 2022年10月22日下午9:08

var mergeTwoLists = function(l1, l2) {
    let dummy = new ListNode(0);
    // 用来保存第一个节点，因为指针也会向前移动
    let temp = dummy;
    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 dummy.next;
};

● 时间复杂度: O(n)
● 空间复杂度: O(1)

0 赞同 0 条回复

晨普通 2022年10月22日下午8:42

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        '''
        初始化
        创建伪节点dum
        创建节点cur指向dum
        '''
        dum = ListNode(0)
        cur = dum
        # 循环合并，当两个链表有一个为空是跳出循环
        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 dum.next

0 赞同 0 条回复

Monster Dump 普通 2022年10月22日下午8:19

实现代码 (Java)

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        while (l1 != null) {
            curr.next = l1;
            l1 = l1.next;
            curr = curr.next;
        }
        while (l2 != null) {
            curr.next = l2;
            l2 = l2.next;
            curr = curr.next;
        }
        return dummy.next;
   }

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

0 赞同 0 条回复

韩杰普通 2022年10月22日下午8:19

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){
            return l2;
        }
        if (l2==null){
            return l1;
        }
        ListNode newlist =new ListNode();
        ListNode temp =newlist;

        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 = l2;
        }else{
            temp.next = l1;
        }

        return newlist.next;
    }
}

0 赞同 0 条回复

lobort 普通 2022年10月22日下午8:02

“`java
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode merge = new ListNode(0);
ListNode temp = merge;
if(l1 == null && l2==null){
return null;
}
if(l1==null && l2!=null){
return l2;
}
if(l2 ==null&& l1 !=null){
return l1;
}
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(L1.length+l2.length) 空间复杂度O(1)

0 赞同 0 条回复

mpweixin用户普通 2022年10月22日下午7:50

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //创建一个新的链表用于返回,给这个链表的头节点设置成虚拟节点，可以同一操作
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;
        //使用双指针法来进行遍历比较，将两个链表中最小的值加入到新链表中
        while(l1!=null&&l2!=null){
            if(l1.val<=l2.val){
                curr.next=l1;
                curr=curr.next;
                //将指针右移一位
                l1=l1.next;
            }else{
                curr.next=l2;
                curr=curr.next;
                l2=l2.next;
            }
        }
        //上述循环直到一个链表整个完全加入到了这个时候将另一个直接全部加入进去
        if(l1!=null){
            curr.next=l1;
        }else{
            curr.next=l2;
        }
        return dummy.next;
    }
}

0 赞同 0 条回复

cxxz 普通 2022年10月22日下午7:31

比较麻烦，麻烦在了一堆特殊情况处理，也是后期要继续学习提高的点，怎么在算法实现中考虑到这些边界情况。由于链表都是有序的，那么就顺序遍历逐对比较就可以了。

ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {

        if (pHead1 == nullptr && pHead2 == nullptr)
            return nullptr;
        else if (pHead2 == nullptr)
            return pHead1;
        else if (pHead1 == nullptr)
            return pHead2;

        ListNode *res = new ListNode(0);
        ListNode *head = new ListNode(0);
        head = res;
        while ( pHead1 != nullptr && pHead2 != nullptr)
        {
            if (pHead1->val <= pHead2->val){
                res->next = pHead1;
                if (pHead1->next == nullptr){
                    pHead1->next = pHead2;
                    return head->next;
                }
                pHead1 = pHead1->next;
            }else{
                res->next = pHead2;
                if (pHead2->next == nullptr){
                    pHead2->next = pHead1;
                    return head->next;
                }
                pHead2 = pHead2->next;
            }
            res = res->next;
        }
        return head->next;
    }

存在两个变量，时间复杂度O(m+n)
空间复杂度O(1)

0 赞同 0 条回复

乱世枭雄普通 2022年10月22日下午7:20

思路：
l1 l2都是从小到大递增的，直接按顺序依次比较，小的放到结果链表

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;
    }
}

0 赞同 0 条回复

泡芙永久会员 2022年10月22日下午7:00

思路：通过比较 l1.val ? l2.val ，谁更小就先放进merge中
时间复杂度：O(M+N)
空间复杂度：O(1)

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        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 dummy.next;
    }
}

0 赞同 0 条回复

绍熙普通 2022年10月22日下午6:41

思路：
创建一个虚拟头结点 dummy 来拼接合并后的链表，cur 代表当前合并链表的末尾位置，同时复用入参的 l1 和 l2 来进行构造。
当 l1 和 l2 均不为空的时候，找到两者中的较小值拼接到 cur 的后面，若 l1 和 l2 任一为空，则将另外的链表拼接完。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode dummy = new ListNode(-1), cur = dummy;
        while (l1 != null || l2 != null) {
            if (l1 != null && l2 != null) {
                if (l1.val < l2.val) {
                    cur.next = l1;
                    cur = cur.next; l1 = l1.next;
                } else {
                    cur.next = l2;
                    cur = cur.next; l2 = l2.next;
                }
            } else if (l1 != null) {
                cur.next = l1;
                cur = cur.next; l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next; l2 = l2.next;
            }
        }
        return dummy.next;
    }
}

0 赞同 0 条回复

酥合普通 2022年10月22日下午6:04

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}

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

此题码住，不想新增额外的节点，但是逻辑变得异常混乱，有时候想太多反而达不到目的。

0 赞同 0 条回复

糖香香普通 2022年10月22日下午5:22

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            //dum为伪头节点，返回的时候需要返回dum.next
            ListNode dum =  new ListNode(0),cur = dum;
            //循环，两个链表都不为空的时候，比较两个链表头节点的值，小的插入链表后面
            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 ? l1 : l2;
            return dum.next;
    }
}

0 赞同 0 条回复

你有点可爱喔普通 2022年10月22日下午5:09

解题思路：
1.比较两个链表的头节点的值，其中头节点较小的值是合并后链表的头节点，，重复步骤。
2.要考虑到两个链表是否为空的情况，这样在相应的判刑下返回出相应的值
时间复杂度O(m+n)
空间复杂度O(m+n)

  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            if(l1==null){
                return l2;
            }else if(l2==null){
                return l1;
            }
            //给出一个节点进行返回
            ListNode temp=null;
            if(l1.val<l2.val){
                temp=l1;
                temp.next=mergeTwoLists(l1.next,l2);
            }else{
                temp=l2;
                temp.next=mergeTwoLists(l2.next,l1);
            }
            return temp;
    }

0 赞同 0 条回复

lone。普通 2022年10月22日下午4:50

class Solution {
        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            //设定一个哨兵节点，方便返回合并后的列表
            ListNode merge = new ListNode(-1);
            //定义一个前置指针
            ListNode prev = merge;

            //每次循环赋值，前置指针下移
            while (l1 != null && l2 != null) {
                if (l1.val <= l2.val) {
                    prev.next = l1;
                    l1 = l1.next;
                } else {
                    prev.next = l2;
                    l2 = l2.next;
                }
                prev = prev.next;
            }

            //可能存在一个链表剩余未放入合并的链表
            prev.next = l1 == null ? l2 : l1;
            return merge.next;
        }
    }

时间复杂度：O(N+M) 取决于两个链表长度

空间复杂度：O(1)

0 赞同 0 条回复

Y7n05h 普通 2022年10月22日下午3:48

“cpp
class Solution {
public:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *head = nullptr;
auto **cur = &head;
if (!l1) return l2;
if (!l2) return l1;
while (true) {
if (l1->val < l2->val) {
*cur = l1;
cur = &l1->next;
l1 = l1->next;
if (!l1) {
*cur = l2;
return head;
}
} else {
*cur = l2;
cur = &l2->next;
l2 = l2->next;
if (!l2) {
*cur = l1;
return head;
}
}
}
}
}

“`

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

0 赞同 0 条回复

小肸永久会员 2022年10月22日下午3:35

思路：就是顺序比较两个链表中节点的大小，按递增的顺序返回一个链表。
递归实现（原链表上进行操作，时间复杂度O(N)，空间复杂度O(N)（递归会有栈开销），N是两个链表的总长度)

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            // 比较l1的下一个节点和l2当前节点
            l1.next = mergeTwoLists(l1.next, l2);
            // 返回l1当前节点
            return l1;
        } else {
            // 比较l2的下一个节点和l1当前节点
            l2.next = mergeTwoLists(l1, l2.next);
            // 返回l2当前节点
            return l2;
        }
    }
}

迭代实现（创建一个新的虚拟头节点，直接在l1、l2上排序，时间复杂度O(N)(N为两个链表的长度)，空间复杂度O(1)（用到了一个虚拟头节点））

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        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 dummy.next;
    } 
}

“`

0 赞同 0 条回复

晨渊普通 2022年10月22日下午3:25

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
          //定义合并排序的链表节点
          ListNode *mergePtr = new ListNode();    //第一个vel=0
          ListNode *merge = mergePtr;
          while((l1!=NULL) && (l2!=NULL)){
          if(l1->val < l2->val){
              merge->next = l1;
              l1 = l1->next;
          }
          else{
              merge->next = l2;
              l2 = l2->next;
          }
          merge = merge->next; //下一个
          }
          merge->next = l1==NULL?l2:l1;    
          return mergePtr->next;      //下一个节点
    }
};

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

0 赞同 0 条回复

追普通 2022年10月22日下午2:14

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *preHead = new ListNode(-1); 
        ListNode *prev = preHead;  //将preHead链表的头节点赋给prev
        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;
        }
        prev->next = l1 == nullptr ? l2 : l1;  //将两个链表中的非空链表接到哨兵列表的最后
        return preHead->next;  //将第一个节点去除（最先开始时赋值该节点值为-1）
    }
};

0 赞同 0 条回复

Haoyun 普通 2022年10月22日下午2:11

// 创建虚拟头结点，遍历l1,l2比较节点值大小，检查没遍历完的链表，返回
时间复杂度：O(n)
空间复杂度:O(1)

var mergeTwoLists = function(l1, l2) {
   let dummy = new ListNode(0);
   let cur = dummy;
   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 dummy.next;
};

0 赞同 0 条回复

潜行1 我是火车王！普通 2022年10月22日下午1:46

时间 O(n)
因为复用原链表的结点，所以空间 O(1)

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    // 套用虚拟头结点的模板
    YourHead := &ListNode{
        Next: nil,
    }
    cur := YourHead

    for l1 != nil || l2 != nil {
        // 下面两个if nil表示其中一个链表已经结束的情况
        if l1 == nil {
            cur.Next = l2
            break
        }
        if l2 == nil {
            cur.Next = l1
            break
        }

        if l1.Val < l2.Val {
            cur.Next = l1
            cur = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            cur = l2
            l2 = l2.Next
        }
    }

    return YourHead.Next
}

0 赞同 0 条回复

虾仁猪心普通 2022年10月22日下午12:12

思路：
1. 先判断这两个链表有没有空链表
2. 创建一个虚拟头节点（dummyHead），并用指针cur指向这个虚拟头节点
3. 遍历list1和list2 并比较节点值的大小
4.跳出循环后指针cur下一个指向的节点是list1和list2当中在上一次循环遍历后还没到链表尾部的链表。
5. 返回虚拟头节点的next指针。
时间复杂度 O（n）
空间复杂度O（1）

public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode dummyHead = new ListNode(Integer.MIN_VALUE);
        ListNode cur = dummyHead;
        ListNode l1 = list1;
        ListNode l2 = list2;
        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 dummyHead.next;
    }
}

0 赞同 0 条回复

派大星普通 2022年10月22日上午11:39

public class Solution3 {
//使用双指针表示当前位置，然后遍历比较大小
//时间复杂度O(n)
//空间复杂度O(1)
    public static ListNode mergeList(ListNode l1,ListNode l2){
        ListNode temp1 = l1;
        ListNode temp2 = l2;
        ListNode l3;
        if(l1 == null&&l2 == null){
            return null;
        }else if (l1 == null){
            return l2;
        } else if (l2 == null) {
            return l1;
        }
        if(temp1.val <= temp2.val) {
            l3 = temp1;
            temp1 = temp1.next;
            while (temp1 != null && temp2 != null) {
                if (temp1.val <= temp2.val) {
                    l3.next = temp1;
                    temp1 = temp1.next;
                    l3 = l3.next;
                } else {
                    l3.next = temp2;
                    temp2 = temp2.next;
                    l3 = l3.next;
                }
            }
            if(temp1 == null){
                l3.next = temp2;
            }else{
                l3.next = temp1;
            }

            return l1;
        }else{
            l3 = temp2;
            temp2 = temp2.next;
            while (temp1 != null && temp2 != null) {
                if (temp1.val <= temp2.val) {
                    l3.next = temp1;
                    temp1 = temp1.next;
                    l3 = l3.next;
                } else {
                    l3.next = temp2;
                    temp2 = temp2.next;
                    l3 = l3.next;
                }
            }
            if(temp1 == null){
                l3.next = temp2;
            }else{
                l3.next = temp1;
            }
            return l2;
        }

    }
}

0 赞同 0 条回复

庄重普通 2022年10月22日上午11:29

 //辅助节点的作用真滴很舒服，不用顾虑头结点的操作
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode merge;
        ListNode* pTmp = &merge;
        //
        for(;l1 != NULL && l2 != NULL;){
            if(l1->val > l2->val){
                pTmp->next = l2;
                l2 = l2->next;
            }
            else{
                pTmp->next = l1;
                l1 = l1->next;
            }
            pTmp = pTmp->next;
        }

        pTmp->next = l1 == NULL ? l2 :l1;

        return merge.next;

    }
};
//时间复杂度：O(m+n) m为l1的长度，n为l2的长度
//空间复杂度：O(1) 只开辟的头结点的内存空间

0 赞同 0 条回复

wxc 普通 2022年10月22日上午10:51

额

class Solution(object):
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if(l1 == None):
            return l2
        elif(l2 == None):
            return l1
        elif(l1.val <= l2.val):
            l1.next = self.mergeTwoLists(l1.next,l2)
            return l1
        else:
            l2.next = self.mergeTwoLists(l1,l2.next)
            return l2

0 赞同 0 条回复

mpweixin用户普通 2022年10月22日上午10:22

遍历两个链表，比较结点大小合并

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

0 赞同 0 条回复

xye 普通 2022年10月22日上午10:07

 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {

    dum := new (ListNode)
    cur := dum

    for l1 != nil && l2 != nil{
        if l1.Val > l2.Val{
            cur.Next = l2
            l2 = l2.Next
        }else{
            cur.Next = l1
            l1 = l1.Next
        }
        cur = cur.Next
    }

    if l2 != nil{
        cur.Next = l2
    }
    if l1 != nil{
        cur.Next = l1
    }
    return dum.Next
}

以上为虚头结点+非递归

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil{
        return l2
    }
    if l2 == nil{
        return l1
    }
    //node := new(ListNode)
    var node *ListNode
    if l1.Val > l2.Val{
        node = l2
        node.Next = mergeTwoLists(l1, l2.Next)
    }else{
        node = l1
        node.Next = mergeTwoLists(l1.Next, l2)
    }
    return node
}

以上为虚节点+递归

0 赞同 0 条回复

是梦终空永久会员 2022年10月22日上午9:56

定义两个新的头结点，l1不大于l2，就把l1插入,或者插入l2
最后肯定有个为空，就把另一个不为空的插入新链表的尾结点
时间复杂度:O(n+m) 两链表之长
空间复杂度:O(1)

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode cur = new ListNode(0);
        ListNode head = cur;
        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;
        if(l2 == null) cur.next = l1;
        return head.next;
    }
}

0 赞同 0 条回复

单个酒窝儿普通 2022年10月22日上午9:45

首先输出特殊情况，当l1为空时，返回l2。当l2为空时，返回l1
1、定义一个值为-1的头节点，在定义一个指针指向头节点
2、当l1和l2同时不为空时，判断l1和l2的值大小，进行链表的构造
3、由于两个链表不一样长，可能会出现l1和l2其中一个为空的情况，此时将剩下的节点拼到构造的链表后边就行
时间复杂度O(n) 空间复杂度O(1)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;

        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 条回复

溴麝香草酚蓝普通 2022年10月22日上午2:04

思路
1. 两个链表都是升序，按顺序比较节点val大小一次放入新建的列表即可；
2. l1,l2分别作为始终指向两个链表头节点的双指针即可，需要新建作为输出的虚拟头节点(resultNode)及其指针，输出resultNode.next即可；
3. 其中一个链表为空直接返回另一个链表即可，不用判断另一个是否为空；
4. 注意循环结束的条件，l1,l2任意一个指针为空就退出循环；
5. 其中一个链表指针到达链尾后，直接把另一个链表剩余的节点放在resultNode的末尾即可。
代码

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode resultNode = new ListNode(0);
        ListNode tmpNode = resultNode;
        int index = 0;
        while (l2 != null && l1 != null) {
            if (l1.val >= l2.val) {
                tmpNode.next = l2;
                l2 = l2.next;
            } else {
                tmpNode.next = l1;
                l1 = l1.next;
            }
            tmpNode = tmpNode.next;
            index += 1;
        }
        if (l1 == null) {
            tmpNode.next = l2;
        } else tmpNode.next = l1;
        return resultNode.next;
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

黎昕普通 2022年10月22日上午1:32

双指针+给l1创建一个虚拟头节点

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *p1=new ListNode();
        p1->next=l1;
        l1=p1;
        ListNode* p2=l2;
        while(p2!=NULL&&p1->next!=NULL){
            if(p1->next->val<=p2->val){
                p1=p1->next;
            }
            else{
                ListNode* temp=p2->next;
                p2->next=p1->next;
                p1->next=p2;
                p2=temp;
            }
        }
        if(p1->next==NULL&&p2!=NULL)p1->next=p2;
        l1=l1->next;
        return l1;  
    }
};

0 赞同 0 条回复

訁訁訁訁訁普通 2022年10月22日上午12:26

时间复杂度O(n+m) nm为两个链表的长度，空间复杂度O(1)

//自己实现
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode cur = new ListNode();
        ListNode ret = cur;
        while(l1 != null && l2 != null){
            if(l2.val >= l1.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        if(l1 == null){
            cur.next = l2;
        }
        if(l2 == null){
            cur.next = l1;
        }
        return ret.next;
    }
}

0 赞同 0 条回复

Error 普通 2022年10月22日上午12:11

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        p1 = l1
        p2 = l2
        res = ListNode(0)
        pre = res
        while l1 and l2:
            if l1.val < l2.val:
                pre.next = l1
                l1 = l1.next
            else:
                pre.next = l2
                l2 = l2.next
            pre = pre.next

        if l1:
            pre.next = l1
        if l2:
            pre.next = l2

        return res.next

时间复杂度 O(n)

0 赞同 0 条回复

Chin 普通 2022年10月22日上午12:03

/**
 * 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) return l2;
        if(l2 == null) return l1;
        ListNode dummyNode = new ListNode(0);
        ListNode cur = dummyNode;
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                cur.next = l1;
                l1 = l1.next;
                cur = cur.next;
            }else {
                cur.next = l2;
                l2 = l2.next;
                cur = cur.next;
            }
        }

        if (l1 == null) {
            cur.next = l2;
        }
        if (l2 == null) {
            cur.next = l1;
        }
        //  哑结点是关键
        return dummyNode.next;
    }
}

时间复杂度O(l1+l2)
空间复杂度O(1)

0 赞同 0 条回复

Spermalow 普通 2022年10月21日下午11:43

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode * merge = new ListNode(0);
        ListNode * t = merge;
        // 当两个链表没有走到头的时候进行以下操作
        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                t->next = l1;
                l1 = l1->next;
            }
            else
            {
                t->next = l2;
                l2 = l2->next;
            }
            // 记得一定要将t的指针往后走
            t = t->next;
        }
        // 如果当某一个指针并没有走到头，说明该指针指向的这个值，大于另一指针最大的值，说明该没有走到最后的指针后面的值都比另一个指针的所有值都大，故可以将其后面的值都接上
        if (l1) t->next = l1;
        else t->next = l2;

        return merge->next;
    }
};

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

0 赞同 0 条回复

马啸天永久会员 2022年10月21日下午11:22

public class Solution {
    public ListNode mergeTwoLists(ListNode l1 , ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode ret = dummyHead;
        if (l1 == null)
            return l2;
        if (l2 == null)
            return l1;
        while (l1 != null && l2 != null) {
            if (l1.val<=l2.val){
                ret.next=l1;
                l1=l1.next;
            }else {
                ret.next=l2;
                l2=l2.next;
            }
            ret=ret.next;
        }
        if (l1==null){
            ret.next=l2;
        }else
            ret.next=l1;
        return dummyHead.next;
    }
}
class Solution2{
    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 条回复

mpweixin用户普通 2022年10月21日下午11:09

/**
 * 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();
        head.next = null;
        ListNode p = head;
        while(l1 != null && l2 != null){            // 将value小的节点加入到新的链表中
            if(l1.val < l2.val){
                p.next = new ListNode(l1.val);
                l1 = l1.next;
            }
            else{
                p.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            p = p.next;
        }
        if(l1 != null)
            p.next = l1;
        if(l2 != null)
            p.next = l2;
        return head.next;
    }
}

// 时间复杂度: O(n)
// 空间复杂度: O(n)

0 赞同 0 条回复

Asphyxia 普通 2022年10月21日下午10:59

思路：穿针引线

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* dump = new ListNode(0);
        ListNode* cur = dump;
        while(pHead1&&pHead2){
            if(pHead1->val<pHead2->val){
                cur->next = pHead1;
                pHead1 = pHead1->next;
            }else{
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
            cur = cur->next;
        }
        cur->next = pHead1==NULL?pHead2:pHead1;
        return dump->next;
    }
};

0 赞同 0 条回复

易水寒永久会员 2022年10月21日下午10:56

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        while(p1 != null && p2 != null) {
            if(p1.val <= p2.val) {
                cur.next = p1;
                p1 = p1.next;
            }
            else {
                cur.next = p2;
                p2 = p2.next;
            }
            cur = cur.next;
        }
        if(p1 != null) {
            cur.next = p1;
        }
        else {
            cur.next = p2;
        }
        return dummy.next;
    }
}
//复杂度O(n)

0 赞同 0 条回复

MR.SandMan 普通 2022年10月21日下午10:13

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

递归

0 赞同 0 条回复

狗蛋儿普通 2022年10月21日下午9:56

还是要创建好虚拟节点，然后注意判断循环的结束与开始

class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* cur = new ListNode(0);
        ListNode* res = cur;
        while (pHead1 && pHead2 ) {
            if (pHead1->val <= pHead2->val) {
                cur-> next = pHead1;
                pHead1 = pHead1-> next;
            } else {
                cur->next = pHead2;
                pHead2  = pHead2->next;
            }
            cur = cur-> next;
        }
        if (pHead1) cur->next = pHead1;
        else cur->next = pHead2;
        return res->next;
    }
};

1 赞同 0 条回复

T 普通 2022年10月21日下午9:45

下面是代码

/**
 * 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  out = new ListNode(0);
        ListNode result = out;
        //同时遍历两个节点
        while(l1 != null && l2 != null) {
            if(l1.val <= l2.val) {
                result.next = l1;
                l1 = l1.next;
            } else {
                result.next = l2;
                l2 = l2.next;
            }
            result = result.next;
        }
        // 把没遍历到空节点的另一个节点接上
        result.next = l1 == null ? l2 : l1;

        return out.next;
    }
}

0 赞同 0 条回复

天然普通 2022年10月21日下午9:41

对python语法不熟悉，and和or在while的关系

# 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):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """

        head = ListNode()
        if not l1:
            return l2
        if not l2:
            return l1
        if  l1.val<l2.val:
            head = l1
            l1 = l1.next     
        else :
            head = l2
            l2 = l2.next
        k=head
        while l1!=None and l2!=None :
            if l1 and l1.val <= l2.val:
                k.next = l1
                l1 = l1.next    
            elif l2:
                k.next = l2
                l2 = l2.next 

            k=k.next
        if l1!=None:
            k.next= l1
        if l2!=None:
            k.next= l2
        return head

0 赞同 0 条回复

青木普通 2022年10月21日下午9:31

//迭代方法
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode p = new ListNode();
        ListNode newList = p; //作为头结点
        //哪个小选哪个
        while(l1 != null && l2 != null){
            if(l1.val > l2.val){
                p.next = l2;
                p = p.next;
                l2 = l2.next;
            }
            else{
                p.next = l1;
                p = p.next;
                l1 = l1.next;
            }
        }
        //如果l1还有剩余，直接加在后面
        if(l1 != null){
            p.next = l1;
        }
        //如果来还有剩余，直接加在后面
        if(l2 != null){
            p.next = l2;
        }
        return newList.next;
    }
}
 //递归方法，这个纯忘光了T T
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        else if(l2==null){
            return l1;
        }
        else if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next, l2);//只要知道这个函数是返回合并好的链表就可以了
            return l1;
        }
        else{
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

1 赞同 0 条回复

So 普通 2022年10月21日下午9:27

第一天第三题

/**
 * 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;
    }
}

0 赞同 0 条回复

如梦似歌普通 2022年10月21日下午9:27

//不会，看的题解
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }else if(l2 == null){
            return l1;
        }else if(l1.val < l2.val){
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }else{
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }
    }
}

0 赞同 0 条回复

194分贝普通 2022年10月21日下午9:02

/*
* 双指针法
*/

class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        ListNode* p = pHead1, *q = pHead2, *virtualHead = new ListNode(0);
        ListNode* r = virtualHead;
        while (p && q) { // 当两个指针都不为空时就一直比较
            p->val < q->val ? (r->next = p, p = p->next) : (r->next = q, q = q->next);
            r = r->next;
        }
        p ? r->next = p : r->next = q;  // 把非空指针后面的结点直接接在后面
        return virtualHead->next;
    }
};

1 赞同 0 条回复

西西弗斯的石头永久会员 2022年10月21日下午8:49

while循环判断刚开始写的l1.next!=null,l2.next!=null，错了

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        //为了确定最终返回的合并链表
        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;
    }
}

0 赞同 0 条回复

王艺超普通 2022年10月21日下午8:44

该题可以用两种办法，一种新建个表头轮流插入

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) return l2;
        if(l2 == NULL) return l1;

        ListNode *head = new ListNode(0);
        ListNode *temp = head;

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

        return head->next;
    }
};

另一种采用递归的思想，面试官应该比较喜欢这种解法

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL) 
        {
            return l2;
        }
        else if(l2 == NULL) 
        {
            return l1;
        }

        else if(l1->val <= l2->val)
        {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }    
        else
        {
            l2->next = mergeTwoLists(l2->next, l1);
            return l2;
        }
    } 
};

“`

0 赞同 0 条回复

一只骆驼普通 2022年10月21日下午8:35

递归

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;
        }

    }
}

迭代

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        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 dummy.next;
    }
}

0 赞同 0 条回复

忆霁昕永久会员 2022年10月21日下午8:29

类似归并排序的merge操作
以前也写过链表上的归并排序，在链表上不用申请额外空间去进行merge操作，使用自下而上的归并排序可以只用O(1)的空间复杂度

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //类似归并排序的merge操作
        ListNode p1 = l1;
        ListNode p2 = l2;
        //结果链表 将遍历到的节点尾插到该链表
        ListNode newHead = new ListNode();
        ListNode tail = newHead;
        while (p1 != null && p2 != null) {
            if (p1.val <= p2.val) {
                tail.next = p1;
                tail = p1;
                p1 = p1.next;
            } else {
                tail.next = p2;
                tail = p2;
                p2 = p2.next;
            }
        }
        //若有一个链表遍历完了，则把另一个链表直接插入到结果链表
        if (p1 != null) {
            tail.next = p1;
        }
        if (p2 != null) {
            tail.next = p2;
        }
        return newHead.next;
    }
}

0 赞同 0 条回复

1ue1uekin8 普通 2022年10月21日下午8:29

来烧脑

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 条回复

zjl 普通 2022年10月21日下午8:20

归并

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode pre = new ListNode();
        ListNode p3 = pre;
        while(p1 != null && p2!=null){
            if(p1.val <= p2.val){
                p3.next = p1;
                p1 = p1.next;
            }else{
                p3.next = p2;
                p2 = p2.next;
            }
            p3 = p3.next;
        }
        while(p1!=null){
            p3.next = p1;
            p3 = p3.next;
            p1 = p1.next;
        }
        while(p2!=null){
            p3.next = p2;
            p3 = p3.next;
            p2 = p2.next;
        }
        return pre.next;

    }

0 赞同 0 条回复

Whatever 永久会员 2022年10月21日下午8:02

注意虚拟头结点的使用，方便返回结果

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode p = l1,q = l2;
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;
        while(p != null && q != null){
            if(p.val > q.val){
                head.next = q;
                q = q.next;
            }else{
                head.next = p;
                p = p.next;
            }
            head = head.next;
        }
        if(p != null){
            head.next = p;
        }
        if(q != null){
            head.next = q;
        }
        return dummy.next;
    }
}

0 赞同 0 条回复

宁永久会员 2022年10月21日下午8:00

构造一个虚拟头节点，注意最后剩余节点的处理方式

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //虚拟头节点
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        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 dummy.next;
    }
}

0 赞同 0 条回复

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

共以下 87 个回答

堆排序写法

还是要创建好虚拟节点，然后注意判断循环的结束与开始

# 回答此问题取消回复

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

共以下 87 个回答

堆排序写法

还是要创建好虚拟节点，然后注意判断循环的结束与开始

# 回答此问题 取消回复

# 回答此问题取消回复