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

招舟子普通 2023年8月24日下午5:08

呜呜打卡

0 赞同 0 条回复

北京西普通 2023年8月2日上午12:32

复杂度O(n+m)，思路跟各位大佬差不多，就是直接新建一个头指针，然后直接插入

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *c,*c1;
    c=(struct ListNode* )malloc(sizeof(struct ListNode));
    c1=c;
    if (l1==NULL)
        return l2;
    if (l2==NULL)
        return l1;
    while (l1!=NULL && l2!=NULL)
    {
        if (l1->val <= l2->val)
        {
            c1->next=l1;
            c1=c1->next;
            l1=l1->next;
        }
        else 
        {
            c1->next=l2;
            c1=c1->next;
            l2=l2->next;
        }
    }
    while (l1!=NULL)
    {
        c1->next=l1;
        c1=c1->next;
        l1=l1->next;
    }
    while (l2!=NULL)
    {
        c1->next=l2;
        c1=c1->next;
        l2=l2->next;
    }
    return c->next;
}

0 赞同 0 条回复

慎言永久会员 2023年7月23日下午4:34

打卡
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode res = new ListNode(-1);
ListNode tail = res;

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

    while(l1 != null){
        tail.next = l1;
        tail = tail.next;
        l1 = l1.next;
    }

    while(l2 != null){
        tail.next = l2;
        tail = tail.next;
        l2 = l2.next;
    }

    return res.next;
}

}

0 赞同 0 条回复

橙子陈普通 2023年7月15日下午5:16

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

        return merge.next;
    }
}

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

0 赞同 0 条回复

ZJS 永久会员 2023年7月9日上午11:32

思路：和归并排序的额最后一步类似
时间复杂度：O(n + m)
空间复杂度：O(1)

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

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

        while(l1 != null){
            tail.next = l1;
            tail = tail.next;
            l1 = l1.next;
        }

        while(l2 != null){
            tail.next = l2;
            tail = tail.next;
            l2 = l2.next;
        }

        return res.next;
    }
}

0 赞同 0 条回复

一琬人间烟火普通 2023年7月7日下午9:40

没啥技巧，纯输出：
c++

class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dnode=new ListNode(0);
ListNode* cur=dnode;
while(l1!=NULL&&l2!=NULL){
if(l1->val>=l2->val){
cur->next=l2;
l2=l2->next;
cur=cur->next;
}else{
cur->next=l1;
l1=l1->next;
cur=cur->next;
}
}
if(l1NULL&&l2!=NULL){
cur->next=l2;
}
if(l1!=NULL&&l2NULL){
cur->next=l1;
}
return dnode->next;
}
};

0 赞同 0 条回复

CaCO3 永久会员 2023年7月7日下午9:38

”’java
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//两个指针

    ListNode head = new ListNode(0);
    ListNode head1 = head;
    while(l1 != null && l2 != null){
        if(l1.val <= l2.val){
            head.next = l1;
            head = l1;
            l1 = l1.next;
        }else{
            head.next = l2;
            head = l2;
            l2 = l2.next;
        }
    }
    if(l1 == null){
        head.next = l2;
    }else{
        head.next = l1;
    }
    return head1.next;
}

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

0 赞同 0 条回复

ᯤ 普通 2023年7月4日下午11:03

双指针交替前进

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

0 赞同 0 条回复

cute. 普通 2023年7月4日上午9:54

思路：使用双指针和虚拟头结点结合，比较两个链表值的大小，然后移动临时指针

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

0 赞同 0 条回复

mpweixin用户永久会员 2023年7月1日上午12:30

代码

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

0 赞同 0 条回复

与你同行普通 2023年6月30日下午5:29

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

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //以此比较l1,l2节点的大小，把比较结果重新指向新的链表
    if l1 == nil {
        return l2
    }
    if l2 == nil {
        return l1
    }

    newList := &ListNode{}
    tail := newList

    for l1 != nil && l2 != nil {
        if l1.Val > l2.Val {
            tmp := l2.Next
            l2.Next = nil

            tail.Next = l2
            tail = tail.Next
            l2 = tmp
        }else {
            tmp := l1.Next
            l1.Next = nil

            tail.Next = l1
            tail = tail.Next
            l1 = tmp
        }
    }

    if l1 == nil {
        tail.Next = l2
    }
    if l2 == nil {
        tail.Next = l1
    }

    return newList.Next
}

0 赞同 0 条回复

昂立的狼普通 2023年6月29日上午9:46

时间复杂度O（n）
空间复杂度O(1)
结果链表，用双指针表示，一个头指针，一个更新指针，
循环比较两个链表，把两个链表中小的值，逐个更新进结果链表，直到其中一个链表为空，则把另外一个链表直接放结果链表后面

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

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

        return res.next

0 赞同 0 条回复

dys 普通 2023年6月28日下午4:26

class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 null) return l2;
if (l2 null) return l1;
ListNode temp = new ListNode(0),curr = temp;
while (l1 != null && l2!=null){
if (l1.val >= l2.val){
curr.next = l2;
l2 = l2.next;
}else{
curr.next = l1;
l1 = l1.next;
}
curr = curr.next;
}
// l1为空，代表没有可以比较的值了，比如l1有三个元素，l2有四个元素，l1在某些比较情况下最后会指向空，这种情况就将curr指向l2剩余的就好了，因为l2时递增排序的
curr.next = l1 != null ? l2 : l1;
return temp.next;
}
}
时间复杂度：O(n+m)，因为需要遍历两个链表。空间复杂度:O(1)

0 赞同 0 条回复

mpweixin用户普通 2023年6月28日下午12:17

java
/**
 * 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(1000);
        ListNode tmp = newlist;
        //定义左右两个指针分别指向两个链表
        ListNode left = l1, right = l2;
        while(left != null && right != null) {
            if(left.val > right.val) {
                tmp.next = right;
                right = right.next;
            } else {
                tmp.next = left;
                left = left.next;
            }
            tmp = tmp.next;
        }
        if(left == null) {
                tmp.next = right;
        }
        if(right == null) {
                tmp.next = left;
        }
        return newlist.next;
    }
}

时间复杂度O(N), 空间复杂度O(N)

0 赞同 0 条回复

浅伤永久会员 2023年6月28日上午11:16

时间复杂度O(n)
空间复杂度O(l1+l2)
由于l1，l2是递增的，因此使用双指针遍历两链表，根据l1.val与l2.val的大小确定添加节点的顺序，交替进行直到遍历完成
创建空链表，引入伪头节点

/**
 * 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 myNode = new ListNode(0);
        ListNode cur = myNode;

        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 myNode.next;
    }
}

或者递归

/**
 * 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;
                    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 条回复

淡色花樱普通 2023年6月28日上午10:13

““java
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.next=l1null?l2:l1;
return merge.next;
}
}
定义一个虚拟头节点，可避免处理空指针的情况

0 赞同 0 条回复

Jerry 普通 2023年6月27日下午10:55

//dummy头节点 + 双指针
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;

        while (l1 != null && l2 != null) {
            // 比较 l1，l2
            // 较小的节点，对接到 curr节点后
            if (l1.val < l2.val) {
                curr.next = l1; //接上
                l1 = l1.next;
            } else {
                curr.next = l2;  //接上
                l2 = l2.next;
            }
            curr = curr.next; //curr节点不断前进
        }

        // 若有另外一个链表未遍历完，则直接接在 curr节点 后
        cur.next = l1 != null ? l1 : l2;

        return dummy.next;// 返回虚拟头节点的 next
    }
}

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

0 赞同 0 条回复

大大普通 2023年6月27日下午9:11

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {//创建一个哑头节点
      ListNode* head=new ListNode();
      ListNode* temp=new ListNode();
      head=temp;
     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;
    if(l2)temp->next=l2;
      return head->next;}
};

0 赞同 0 条回复

Lucky 普通 2023年6月27日下午4:22

python3实现
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
cur = dum = ListNode(0)
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 条回复

mpweixin用户普通 2023年6月26日下午10:52

设置辅助节点
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 条回复

泡芙永久会员 2023年6月26日下午5:36

用一个虚拟头节点，避免处理空指针的情况
类似于”拉拉链“，l1, l2 就相当于拉链两侧的锯齿，指针 cur 就好像拉链的拉索，将两个有序链表合并
Time：O(M+N)
Space：O(1)

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

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

Gracelyne 普通 2023年6月25日下午3:14

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode();
        ListNode *temp = dummy; //dummy和temp指向位置相同

        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;
        if(l2) temp->next = l2;
        return dummy->next;
    }

0 赞同 0 条回复

Yangon 普通 2023年6月25日上午10:23

合并

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newTemp = new ListNode(0);
        ListNode temp = newTemp;

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

        temp.next = l1 == null ? l2 : l1;
        return newTemp.next;


    }
}

0 赞同 0 条回复

HU 普通 2023年6月24日下午7:16

/**
 * 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 res = new ListNode(0);
    let temp = res;

    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 res.next;
};

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

0 赞同 0 条回复

baoyou 普通 2023年6月24日下午6:33

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

使用辅助节点避免频繁判断null

0 赞同 0 条回复

往远处看普通 2023年6月24日上午11:02

解题思路

创建一个空头节点，ListNode res = new ListNode(0),p = res（这个要记下来），用于将两个链表合并到这个节点后面。创建一个指针p指向这个空头节点，用于指向这个空链表的最后一个节点。通过比较L1和L2链表节点的值，哪个节点值小，就将空头节点的next指向哪个节点。下一步，比如L1节点的值更小，空头节点指向它以后，L链表指针往后移动一个。继续比较，直到这两个链表中有一个链表遍历完了，剩下没遍历完的链表接在新链表后面。

代码

“`cpp
/**
* 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 *res = new ListNode(0),*p = res;
//如果某个链表为空链表，则直接返回另外一个链表
if(!l1) return l2;
if(!l2) return l1;
while(l1 && l2)
{
l1->val > l2->val ?(p->next = l2,l2 = l2->next):(p->next = l1,l1 = l1->next);
p = p->next;
}
if(!l1)
{
p->next = l2;
return res->next;
}
else
{
p->next = l1;
return res->next;
};

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

0 赞同 0 条回复

已断网的Blue 普通 2023年6月24日上午10:00

创建辅助节点

“`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 *t = new ListNode(-1);
t->next = NULL;
ListNode *cur = t;
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;
else cur->next = l2;

    return t->next;

}

};

“`

0 赞同 0 条回复

mpweixin用户普通 2023年6月23日下午9:00

注意使用头节点辅助节点

/**
 * 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 l1Node = l1;
        ListNode l2Node = l2;
        ListNode tmpNode = new ListNode(0);
        ListNode newHead = tmpNode;

        while(l1Node!=null && l2Node!=null) {
            if (l1Node.val <= l2Node.val){
                tmpNode.next = l1Node;
                l1Node = l1Node.next;
            }else{
                tmpNode.next = l2Node;
                l2Node = l2Node.next; 
            }
            tmpNode = tmpNode.next;

        }

        tmpNode.next = l1Node == null ? l2Node : l1Node;

        return newHead.next;

    }
}

0 赞同 0 条回复

未来已来~ 普通 2023年6月23日上午11:46

/** Java 代码
 * 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) {
        //是否为null判断
        if(l1 == null && l2 == null) return null;
        if(l1 == null) return l2;
        if(l2 == null) return l1;

        ListNode mergeList = new ListNode(0); // 初始化辅助节点(伪头节点)作为接收俩链表合并后的链表
        ListNode temp = mergeList;

        while(l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                temp.next = l1; // 设置辅助节点为避免 temp为空指针时,temp.next报异常,否则每次需判断temp是否为空
                l1 = l1.next; // 指针往下递归遍历
            } else { // l1 >= l2
                temp.next = l2;
                l2 = l2.next;
            }

            temp = temp.next; // 把每次比较的结果赋值到temp临时链表中
        }

        temp.next = l1 == null ? l2 : l1; // 俩链表不同时遍历完成(不同时指向null结束)

        return mergeList.next; // 返回合并后的链表,注意merge头结点为伪节点

    }
}

复杂度分析：
时间复杂度: O(M+N) ： M,N 分别为链表 l1,l2 的长度，合并操作需遍历两链表。
空间复杂度: O(1) ：节点引用 mergeList, temp使用常数大小的额外空间。

1 赞同 0 条回复

TT 永久会员 2023年6月22日下午9: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;
        }
    }
}

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

0 赞同 0 条回复

WhyBeBubble 普通 2023年6月22日下午5:34

“`C++
class Solution {
//实现
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

    ListNode *dummy = new ListNode(0);
    ListNode *h1 = l1, *h2 = l2, *curr = dummy;
    while (h1 && h2) {
        if(h1->val < h2->val) {
            curr->next = h1;
            h1 = h1->next;
        } else {
            curr->next = h2;
            h2 = h2->next;
        }
        curr = curr->next;
    }
    if(h1) curr->next = h1;
    if(h2) curr->next = h2;
    return dummy->next;
}

};

“`

0 赞同 0 条回复

Yodl. 普通 2023年6月22日下午12:30

/**
 * 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=l1;
        ListNode* q=l2;
        ListNode* r=new ListNode(0);
        r->next=p;
        ListNode* s=r;
        while(p!=NULL&&q!=NULL)
        {
            if(p->val<q->val)
            {
                p=p->next;
                r=r->next;
            }
            else if(p->val==q->val)
            {
                p=p->next;
                r=r->next;
                r->next=q;
                q=q->next;
                r->next->next=p;
                r=r->next;
            }
            else
            {
                r->next=q;
                q=q->next;
                r->next->next=p;
                r=r->next;
            }
        }
        if(p==NULL)
        {
            r->next=q;
        }
        return s->next;
    }
};

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

0 赞同 0 条回复

等待普通 2023年6月22日上午10:09

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//新建一个链表对象，用于存放merge后的链表结果
ListNode mergeListNode = new ListNode();
ListNode temp = mergeListNode;
//非空判断
if (l1null&&l2null){
return null;
}
while(l1!=null && l2!=null) {
if (l1.val < l2.val) {
mergeListNode.next = l1;
mergeListNode = mergeListNode.next;
l1 = l1.next;
} else {
mergeListNode.next = l2;
mergeListNode = mergeListNode.next;
l2 = l2.next;
}
}
if (l2!=null){
mergeListNode.next = l2;
}else if (l1!=null){
mergeListNode.next = l1;
}
return temp.next;
}

0 赞同 0 条回复

等待普通 2023年6月22日上午10:09

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//新建一个链表对象，用于存放merge后的链表结果
ListNode mergeListNode = new ListNode();
ListNode temp = mergeListNode;
//非空判断
if (l1null&&l2null){
return null;
}
while(l1!=null && l2!=null) {
if (l1.val < l2.val) {
mergeListNode.next = l1;
mergeListNode = mergeListNode.next;
l1 = l1.next;
} else {
mergeListNode.next = l2;
mergeListNode = mergeListNode.next;
l2 = l2.next;
}
}
if (l2!=null){
mergeListNode.next = l2;
}else if (l1!=null){
mergeListNode.next = l1;
}
return temp.next;
}

0 赞同 0 条回复

等待普通 2023年6月22日上午10:09

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//新建一个链表对象，用于存放merge后的链表结果
ListNode mergeListNode = new ListNode();
ListNode temp = mergeListNode;
//非空判断
if (l1null&&l2null){
return null;
}
while(l1!=null && l2!=null) {
if (l1.val < l2.val) {
mergeListNode.next = l1;
mergeListNode = mergeListNode.next;
l1 = l1.next;
} else {
mergeListNode.next = l2;
mergeListNode = mergeListNode.next;
l2 = l2.next;
}
}
if (l2!=null){
mergeListNode.next = l2;
}else if (l1!=null){
mergeListNode.next = l1;
}
return temp.next;
}

0 赞同 0 条回复

等待普通 2023年6月22日上午10:09

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//新建一个链表对象，用于存放merge后的链表结果
ListNode mergeListNode = new ListNode();
ListNode temp = mergeListNode;
//非空判断
if (l1null&&l2null){
return null;
}
while(l1!=null && l2!=null) {
if (l1.val < l2.val) {
mergeListNode.next = l1;
mergeListNode = mergeListNode.next;
l1 = l1.next;
} else {
mergeListNode.next = l2;
mergeListNode = mergeListNode.next;
l2 = l2.next;
}
}
if (l2!=null){
mergeListNode.next = l2;
}else if (l1!=null){
mergeListNode.next = l1;
}
return temp.next;
}

0 赞同 0 条回复

等待普通 2023年6月22日上午10:09

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//新建一个链表对象，用于存放merge后的链表结果
ListNode mergeListNode = new ListNode();
ListNode temp = mergeListNode;
//非空判断
if (l1null&&l2null){
return null;
}
while(l1!=null && l2!=null) {
if (l1.val < l2.val) {
mergeListNode.next = l1;
mergeListNode = mergeListNode.next;
l1 = l1.next;
} else {
mergeListNode.next = l2;
mergeListNode = mergeListNode.next;
l2 = l2.next;
}
}
if (l2!=null){
mergeListNode.next = l2;
}else if (l1!=null){
mergeListNode.next = l1;
}
return temp.next;
}

0 赞同 0 条回复

短某人。永久会员 2023年6月22日上午12:33

打卡

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        cur = dum = ListNode(0)
        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 条回复

CV大神普通 2023年6月22日上午12:08

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//递归的终结条件
        if(l1 ==null){
            return l2;
        }
        //递归的终结条件
        if(l2 == null){
            return l1;
        }
        //如果l1第一个比l2第一个小，毫无疑问l1第一个是头结点，l1.next在l2和l1.next两者之间产生
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {//同理，如果l2第一个比l1第一个小，毫无疑问l2第一个是头结点，l2.next在l1和l2.next两者之间产生
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }

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

0 赞同 0 条回复

地平线真勇敢普通 2023年6月21日下午11:00

Java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode merge = new ListNode(0);   //辅助节点
        ListNode temp = merge;

        while(l1 !=null && l2!= null ){ //对l1和l2链表的节点进行依次判断
            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 == null ? l2 : l1;
        return merge.next;

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

0 赞同 0 条回复

mpweixin用户普通 2023年6月21日下午9:04


//使用虚拟头结点，不需要单独考虑头结点的情况
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }
        //将l2合并l1,给l1增加虚拟头结点
        ListNode node = new ListNode();
        node.next = l1;
        ListNode p1 = node;
        ListNode p2 = l2;
        while(p1.next != null && p2 != null){
            while(p1.next != null && p1.next.val < p2.val){
                //找到l1中大于/等于p2的结点的前一个结点
                p1 = p1.next;
            }
            //p2添加到p1后
            ListNode temp = p2.next;
            p2.next = p1.next;
            p1.next = p2;
            p2 = temp;
            //p1不应该移动
        }
        if(p1.next == null){
            p1.next = p2;
        }
        return node.next;
    }
}

//方法二
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
       //重新构建一条链表,设置虚拟头结点
       ListNode node = new ListNode();
       ListNode p = node;
       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;
       }
       p.next = l1 != null ? l1 : l2;
       return node.next;
    }
}

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

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月21日下午7:21

打卡

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

    if(l1 == null){
        temp.next = l2;
    }else{
        temp.next = l1;
    }

    return merge.next;
};

0 赞同 0 条回复

3_🔥 永久会员 2023年6月21日下午4:27

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?l1:l2;
        return merge.next;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月21日下午3:51

双指针

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

class Solution:
    def getKthFromEnd(self, head: ListNode, k: int) -> ListNode:
        pre, cur = head, head
        for _ in range(1, k):
            cur = cur.next

        while cur.next != None:
            pre = pre.next
            cur = cur.next

        return pre

0 赞同 0 条回复

&Camille 普通 2023年6月21日上午7:51

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

    //指针l3用于移动链表，l4用于返回链表
    ListNode l3 = new ListNode(-1);
    ListNode l4=l3;

    //遍历链表
    while(l1!=null&&l2!=null){
    if(l1.val<=l2.val){
            l3.next=l1;
            l1=l1.next;
        }
        else if(l1.val>l2.val){
            l3.next=l2;
            l2=l2.next;
        }
        l3=l3.next;
    }
    while(l2!=null){
        l3.next=l2;
        l2=l2.next;
        l3=l3.next;
    }
    while(l1!=null){
        l3.next=l1;
        l1=l1.next;
        l3=l3.next;
    }
    return l4.next;
}

}

0 赞同 0 条回复

哈哈哈哈开开心心普通 2023年6月21日上午6:44

# 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 not l1:
            return l2
        elif not l2:
            return l1

        cur_l1 = l1
        cur_l2 = l2
        # 创建结果的表头
        res = ListNode()
        cur_l3 = res

        while cur_l1 and cur_l2:
            if cur_l1.val < cur_l2.val:
                cur_l3.next = cur_l1
                cur_l1 = cur_l1.next
            else:
                cur_l3.next = cur_l2
                cur_l2 = cur_l2.next
            cur_l3 = cur_l3.next

        if not cur_l1:
            cur_l3.next = cur_l2
        elif not cur_l2:
            cur_l3.next = cur_l1

        return res.next

0 赞同 0 条回复

mpweixin用户普通 2023年6月21日上午12:03

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
 struct ListNode *t=malloc(sizeof(struct ListNode)),*q=malloc(sizeof(struct ListNode));
    if(!l1&&!l2) return NULL;     
    if(!l1) return l2;      
    if(!l2) return l1;    //特殊情况判断 
    if(l1->val<l2->val){
        t=l1;
        q=t;
        l1=l1->next;
        t->next=NULL;
    }else{
        t=l2;
        q=t;
        l2=l2->next;
        t->next=NULL;
    }
    while(l1&&l2){
    if(l1->val<l2->val){
        q->next=l1;
        q=q->next;
        l1=l1->next;
    }else{
        q->next=l2;
        q=q->next;
        l2=l2->next;
    }
    }
    if(!l1)
        q->next=l2;
    else 
        q->next=l1;
    return t;


}

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

0 赞同 0 条回复

mpweixin用户普通 2023年6月20日下午9:20

伪头节点
# 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:
        p = l1
        q = l2
        res = ListNode(0)
        tmp = res
        while p and q:
            if p.val >= q.val:
                tmp.next = q
                q = q.next
            else:
                tmp.next = p
                p = p.next
            tmp = tmp.next
        tmp.next = p if p else q
        return res.next

0 赞同 0 条回复

mpweixin用户普通 2023年6月20日下午7:26

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

顺序遍历，虚拟头节点 O(n+m) O(1)

0 赞同 0 条回复

mpweixin用户普通 2023年6月20日下午6:43

C++实现时间复杂度O(n) 空间复杂度O(1) 创建一个虚拟头结点然后利用双指针的思想比较两个链表中数据较小的结点将它加入虚拟节点后然后重复下去

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

        ListNode *dummyHead = new ListNode(0);
        ListNode *cur = dummyHead;
        ListNode *n1 = l1;
        ListNode *n2 = l2;

        while( n1 != NULL && n2 != NULL){
            if( n1 -> val <= n2 -> val){
                cur -> next = n1;
                n1 = n1 -> next;
            }else{
                cur -> next = n2;
                n2 = n2 -> next;
            }
            cur = cur -> next;
        }
        if(n1 == NULL && n2 != NULL){
            cur -> next = n2;
        }
        if(n1 != NULL && n2 == NULL){
            cur -> next = n1;
        }
        ListNode *head = dummyHead -> next;
        return head;
    }
};

0 赞同 0 条回复

别恰冰水🧊 永久会员 2023年6月20日下午6:29

“`java
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;
    }

    if(l1 == null){
        temp.next = l2;
    }
    if(l2 == null){
        temp.next = l1;
    }

    return merge.next;
}

}

0 赞同 0 条回复

普通 2023年6月20日下午6:05

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode node = new ListNode(0);
        ListNode index = node;
        while(l1 != null || l2 != null){
            if(l1 == null){
                index.next = new ListNode(l2.val);
                l2 = l2.next;
                index = index.next;
                continue;
            }
            if(l2 == null){
                index.next = new ListNode(l1.val);
                l1 = l1.next;
                index = index.next;
                continue;
            }
            if(l1.val >= l2.val){
                index.next = new ListNode(l2.val);
                l2 = l2.next;
            }else{
                index.next =  new ListNode(l1.val);
                l1 = l1.next;
            }
            index = index.next;
        }
        return node.next;
    }
}

创建伪头节点，判断if(l1.val >= l2.val)则将l2.val添加进链表再将l2向前走一步,反之前进l1

0 赞同 0 条回复

mpweixin用户普通 2023年6月20日下午4:01

# 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:
        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 # 核心

        cur.next = l1 if l1 else l2

        return dummy.next

定义一个虚拟头节点dummy，使用cur始终指向合并链表的头节点。

0 赞同 0 条回复

断舍离永久会员 2023年6月20日下午3:11

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //1个辅助节点，可以节约后面的判null条件
        ListNode merge = new ListNode(0);
        ListNode temp = merge;

        //当两链表有一个为null时，结束循环
        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后面
        if(l1 == null){
            temp.next = l2;
        }else {
            temp.next = l1;
        }

        //返回辅助节点的下一节点，就是合并列表的头节点
        return merge.next;
    }
}

0 赞同 0 条回复

BOZ 普通 2023年6月20日下午2:51

记录合并链表的header，定义一个temp指针，接下来往temp指针后依次添加l1/l2中更小的节点即可，时间复杂度O(m+n)，空间复杂度O(1)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *head = new ListNode(0);
        ListNode *curr = head;

        while(true) {
            if (l1 == NULL) {
                curr->next = l2; break;
            } else if (l2 == NULL) {
                curr->next = l1; break;
            }

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

0 赞同 0 条回复

Bello~ 普通 2023年6月20日下午12:38

合并到一个新链表，此法比较简单，也可在将两个链表合并到其中一个链表，能节省空间复杂度

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 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;
        }
        if (l2 == null) {
            cur.next = l1;
        }
        return head.next;
    }
}

0 赞同 0 条回复

小柒叻普通 2023年6月20日下午12:19

剑指 Offer 25. 合并两个排序的链表
依次比较大小

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

0 赞同 0 条回复

名字什么的好麻烦普通 2023年6月20日上午11:23

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

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

0 赞同 0 条回复

张开怀普通 2023年6月20日上午10:35

class Solution {
public:
       ListNode* mergeTwoLists(ListNode* l1, ListNode* l2){
             % 创建辅助结点，未使用辅助结点的话，若temp为空指针，其指向的下一个结点会出现异常
             % 若没有使用辅助结点，也可以进行判断是否为空进行处理，但会加大代码量
             ListNode* merge = new ListNode(0);
             ListNode* temp = merge;
             % 两链表同时不为空进入下面循环
             while(l1 && 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 ? l1 : l2;
             return merge->next;
       }
}

0 赞同 0 条回复

mpweixin用户普通 2023年6月20日上午10:19

C++实现

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

0 赞同 0 条回复

硬核洋葱普通 2023年6月20日上午9:44

/**
 * 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 *p1 = l1, *p2 = l2;
        ListNode *dummyhead = new ListNode(0);
        ListNode *p = dummyhead;
        while(p1 && p2){
            int pval;
            if(p1->val <= p2->val){
                pval = p1->val;
                p1 = p1->next;
            }
            else{
                pval = p2->val;
                p2 = p2->next;
            }   
            ListNode* newnode = new ListNode(pval);
            p->next = newnode;
            p = newnode;
        }
        if(!p1)
            p1 = p2;
        while(p1){
            ListNode* newnode = new ListNode(p1->val);
            p->next = newnode;
            p = newnode;
            p1 = p1->next;
        }
        return dummyhead->next;
    }
};

时间复杂度 O(m+n)，空间 O(m+n)，主要是弄了个新链表用新节点存放合并结果，但是也可以用原节点存放结果

0 赞同 0 条回复

花老爷普通 2023年6月20日上午9:08

直接遍历
时间：O(m+n)
空间：O(1)

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

0 赞同 0 条回复

mpweixin用户普通 2023年6月20日上午4:03

c++
使用双指针，每个指针指向一个链表的头节点。不断比较两个指针的值，将小节点的放入到新构建的链表，直到遍历完其中一个链表。然后把剩下的链表接在构建好的链表的尾部即可。
TC: O(n)
SC: O(1)

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(0);
        ListNode *curr = dummy;
        ListNode *curr1 = l1;
        ListNode *curr2 = l2;
        while (curr1 && curr2) {
            if (curr1->val <= curr2->val) {
                curr->next = curr1;
                curr1 = curr1->next;
            } else {
                curr->next = curr2;
                curr2 = curr2->next;
            }
            curr = curr->next;
            curr->next = NULL;
        }
        curr->next = curr1 ? curr1 : curr2;
        return dummy->next;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年6月19日下午11:54

“`c#
public ListNode MergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode temp = head;

    while(l1 != null || l2 != null){

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

        temp = temp.next;

    }

    return head.next;
}

“`
循环的判断条件，头节点的设置与保存

0 赞同 0 条回复

彦，，# 普通 2023年6月19日下午11:53

不管怎么样，也是自己写出来的。啊啊啊

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

0 赞同 0 条回复

　　　　　　　　普通 2023年6月19日下午11:52

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* res=new ListNode(0),*cur=res;
        while(l1&&l2){
            if(l1->val>l2->val){
                cur->next=l2;
                cur=cur->next;
                l2=l2->next;
            }
            else{
                cur->next=l1;
                cur=cur->next;
                l1=l1->next;
            }
        }
        if(l1)cur->next=l1;
        if(l2)cur->next=l2;
        return res->next;
    }
};

【时间O(m+n),空间O(1)】
从头比较两个链表节点
将小的接到cur节点后面
将剩余链表接到cur节点后面
返回头结点

0 赞同 0 条回复

大鑫啊普通 2023年6月19日下午11:44

时间复杂度：O(m+n)
空间复杂度：O(1)
1、先创建合并之后的头结点以及头结点的next结点temp
2、在两个待合并链表头结点非空的条件下循环
3、哪个头结点值小，则将temp的next节点指向该节点，并该头结点往后移
4、判断一次大小后，将temp结点往后移
5、循环结束后，用三元运算符将temp的next结点指向未遍历到结尾的链表的头结点

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

1 赞同 0 条回复

残月冷骄阳普通 2023年6月19日下午11:43

/**
 * 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) {

<pre><code>    ListNode  head = new ListNode(-1);

    ListNode next = head;

//移动最小的节点。
    while (l1 !=null && l2!=null){
        if(l1.val < l2.val){
            next.next = l1;
            l1 = l1.next;
        }else{
            next.next=l2;
            l2 = l2.next;
        }
        next = next.next;
    }
    //处理完还有一个为非null情况，需要续上。
    next.next = l1==null?l2:l1;
    return head.next;
}

}

0 赞同 0 条回复

Tral-JQ 普通 2023年6月19日下午11:42

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //递归方法
        if(l1 == nullptr) return l2;
        if(l2 == nullptr) return l1;

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

1 赞同 0 条回复

yxy 普通 2023年6月19日下午11:37

/**
 * 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;
        ListNode* cur = dummy;
        ListNode* p1 = l1;
        ListNode* p2 = l2;
        while(p1&&p2)
        {
            if(p1->val<p2->val)
            {
                cur->next = p1;
                cur=cur->next;
                p1=p1->next;
            }
            else
            {
                cur->next = p2;
                cur=cur->next;
                p2=p2->next;
            }
        }
        if(p1)
        {
            cur->next=p1;
        }
        else
            cur->next=p2;
        return dummy->next;
    }
};

有难度

0 赞同 0 条回复

张君雅小妹妹普通 2023年6月19日下午11:18

时间复杂度：O(m + n) m为l1的节点个数，n为l2的节点个数
空间复杂度：O(1)

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

0 赞同 0 条回复

怀瑾永久会员 2023年6月19日下午11:10

C++
执行用时：
16 ms
内存消耗：
18.7 MB
合并两个排序的链表：
采用双指针的方式：
首先创建一个新的头节点，接着判断被排序链表的头节点的值的大小关系

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* l3=new ListNode(0);
        ListNode* l4=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;
        }
        l3->next = l1 == NULL ? l2 : l1;
        return l4->next;
    }
};

0 赞同 0 条回复

钱杰普通 2023年6月19日下午10:53

class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1:
return l2
if not l2:
return l1
res=ListNode(0)
cur=res
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 res.next
”’
1 分别判断l1和l2两个链表是否为空，如果一方为空，则返回另一方即可
2 设立一个头结点res,用cur指针，指向头结点
3接着是存在的一个阶段，就是l1和l2都不为空，互相比对l1和l2的值，哪一方小，指针的下一个对象就是哪一方，在此基础上，哪一方的值被后面的那个值替代，指针相当于原先这个位置走过了，接下来走到下一个位置，即cur=cur.next
4进入下一个阶段，那就是一方比另一方短，如果上个阶段走完还有的话，换句话说，有一个链表已经为空，在此基础上，cur的下一个对象就是不为空的那个
5指针走完，新的节点已经生成，忽略我刚刚加上的头结点res，选择res.next
时间复杂度O(n)，空间复杂度O(1)
”’

0 赞同 0 条回复

Sexypig. 普通 2023年6月19日下午10:52

代码：

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // 虚拟头结点
    ListNode dummy = new ListNode(-1), p = dummy;
    ListNode p1 = l1, p2 = l2;

    while (p1 != null && p2 != null) {
        // 比较 p1 和 p2 两个指针
        // 将值较小的的节点接到 p 指针
        if (p1.val > p2.val) {
            p.next = p2;
            p2 = p2.next;
        } else {
            p.next = p1;
            p1 = p1.next;
        }
        // p 指针不断前进
        p = p.next;
    }

    if (p1 != null) {
        p.next = p1;
    }

    if (p2 != null) {
        p.next = p2;
    }

    return dummy.next;
}

0 赞同 0 条回复

跋扈疙瘩汤普通 2023年6月19日下午10:43

我真笨，提交了5次才AC

/**
 * 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) return l2;
        if (!l2) return l1;

        vector<int> nums;
        while (l1 && l2) {
            nums.push_back(l1->val);
            nums.push_back(l2->val);
            l1 = l1->next;
            l2 = l2->next;
        }

        while (l1) {
            nums.push_back(l1->val);
            l1 = l1->next;
        }

        while (l2) {
            nums.push_back(l2->val);
            l2 = l2->next;
        }

        sort(nums.begin(), nums.end());

        ListNode* dummy = new ListNode(0);
        ListNode* cur = dummy;
        for (int i = 0; i < nums.size(); i++) {
            cur->next = new ListNode(nums[i]);
            cur = cur->next;
        }

        return dummy->next;
    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年6月19日下午10:42

思路分析：
1.首先创建一个虚拟节点(dummy)，并用变量p指向它。这个虚拟节点将作为合并后的链表的头部。
2.创建两个指针p1和p2，分别指向两个输入链表l1和l2的头节点。
3.使用while循环，只要p1和p2都不为空，就进行以下操作：
4.如果p1的值大于p2的值，说明p2所指向的节点应该排在当前节点之后，因此将p2所指向的节点连接到p的后面，并将p2指针向后移动一位。否则，将p1所指向的节点连接到p的后面，并将p1指针向后移动一位。
5.最后，将p指针向后移动一位，准备连接下一个节点。
6.当其中一个链表遍历完毕后，可能还有剩余节点。此时，将剩余链表的所有节点直接连接到p的后面。
7.最后，返回虚拟节点dummy的下一个节点，即合并后的链表的头节点。

时间复杂度为O(m+n)，m和n分别是两个输入链表的长度，因为我们需要遍历两个链表的所有节点。

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1), p = dummy;
        ListNode p1 = l1;
        ListNode p2 = l2;

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

        if(p1 != null){
            p.next = p1;
        }

        if(p2 != null){
            p.next = p2;
        }
        return dummy.next;
    }
}

0 赞同 0 条回复

zll 普通 2023年6月19日下午10:38

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *p,*q;
    if(!l1&&!l2)
        return NULL;
    else if(!l1)
        return l2;
    else if(!l2)
        return l1;
    if(l1->val<l2->val){
        p=l1;
        q=p;
        l1=l1->next;
        p->next=NULL;
    }else{
        p=l2;
        q=p;
        l2=l2->next;
        p->next=NULL;
    }
    while(l1&&l2){
    if(l1->val<l2->val){
        q->next=l1;
        q=q->next;
        l1=l1->next;
    }else{
        q->next=l2;
        q=q->next;
        l2=l2->next;
    }
    }
    if(!l1)
        q->next=l2;
    else 
        q->next=l1;
    return p;
}

0 赞同 0 条回复

阿白普通 2023年6月19日下午10:35

思路：新建一个头节点，比较两个排序链表大小，小的连到新节点后，直到一个链表遍历完，将另一个链表剩余部分全部连接到新链表中
复杂度：时间复杂度O（m+n）空间复杂度O（1）

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


    }

0 赞同 0 条回复

哈哈哈普通 2023年6月19日下午10:30

思路：采用空间换时间的办法。这里仍然使用虚拟节点，result、step含有虚拟头节点，子节点为l1.当step.next与l2不为空时，且step.next.val>=l2.val时，在step.next之前插入与l2.val相等的节点，直至小于为止；如果小于时，则移动step节点，但仍然以step.next节点的val进行比较，如此主要是为了防止节点为空时无法比较的情况。最后需要注意的是，当step.next为空时，说明l1到头，将l2节点连接在其后即可；当l2为空则不进行操作。最后返回result.next链表即可。（描述的过程有点乱，但本人的思路是清晰的）

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
         ListNode result=new ListNode();
         result.next=l1;
        ListNode step=result;
        while(step.next!=null&&l2!=null){
            if(step.next.val>=l2.val){
            ListNode cur=new ListNode(l2.val);
            cur.next=step.next;
            step.next=cur;
            step=cur;
            l2=l2.next;
            }else{
                step=step.next;
            }
        }
        if(step.next==null){
            step.next=l2;
        }
       return result.next;

    }
}

0 赞同 0 条回复

江畅普通 2023年6月19日下午10:24

“`C++
class Solution {
public:
// 递归写法
// 时间复杂度 O(N + M)，两个链表节点数和
// 空间复杂度 O(N + M)，每次递归会新开辟栈空间
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1 == nullptr) { return l2; }
else if (l2 == nullptr) { 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;
}
};
};

class Solution {
public:
// 迭代写法
// 时间复杂度 O(N + M)，两个链表节点数和
// 空间复杂度 O(1)
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummyHead = new ListNode(0);
ListNode* cur = dummyHead;

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

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

    ListNode* res = dummyHead->next;
    delete dummyHead;
    return res;
}

};

“`

0 赞同 0 条回复

mpweixin用户永久会员 2023年6月19日下午10:09

//时间复杂度O(min(m,n))，空间复杂度O(1)
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode xuHead = new ListNode(-1);

        ListNode cur = xuHead;
        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 xuHead.next;
    }

0 赞同 0 条回复

désire. 普通 2023年6月19日下午10:04

C++实现
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 NULL) return l2;
if(l2 NULL) return l1;
ListNode* newlist = new ListNode(0);
ListNode* tmp = newlist;
while(l1 && l2 ){
if(l1->val <= l2->val){
tmp->next = l1;
l1 = l1->next;
}
else{
tmp->next = l2;
l2 = l2->next;
}
tmp = tmp->next;
}

    tmp->next = l1  ? l1 : l2;

    return newlist->next;
}

};

0 赞同 0 条回复

Tang 普通 2023年6月19日下午9:58

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;
        }
        l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
}

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

0 赞同 0 条回复

mpweixin用户普通 2023年6月19日下午9:49

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *root=new ListNode(0);
        ListNode *cur=root;
        while(l1!=nullptr && l2!=nullptr)
        {
            if(l1->val>l2->val)
            {
                ListNode *temp=l2->next;
                cur->next=l2;
                l2=temp;
                cur=cur->next;
            }
            else
            {
                ListNode *temp=l1->next;
                cur->next=l1;
                l1=temp;
                cur=cur->next;
            }

        }
        if(l1!=nullptr)
        {
            cur->next=l1;
        }
        if(l2!=nullptr)
        {
            cur->next=l2;
        }
        return root->next;
    }
};

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

0 赞同 0 条回复

～普通 2023年6月19日下午9:48

c++代码
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(-1);
ListNode* p1 = l1, p2 = l2;
ListNode p = dummy;
while(p1!=nullptr&&p2!=nullptr){
if(p1->valval){
p->next = p1;
p1 = p1->next;
}
else{
p->next = p2;
p2 = p2->next;
}
p = p->next;
}
if(p1!=nullptr){
p->next = p1;
}
if(p2!=nullptr){
p->next = p2;
}
return dummy->next;
}
};

0 赞同 0 条回复

小吕普通 2023年6月19日下午9:46

c++实现
ListNode* phead = new ListNode(-1);
ListNode* pre = phead;
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 = l1NULL?l2:l1;
return phead->next;

0 赞同 0 条回复

mpweixin用户普通 2023年6月19日下午9:45

c++实现
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 NULL){
return l2;
}
if(l2 NULL){
return l1;
}
// 创建一个新的链表
ListNode * mergeList = new ListNode;
ListNode * cur = mergeList;
while(l1 && 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 NULL ? l2 : l1;
return mergeList->next;
}
};
时间复杂度O(M+N),分别是两个链表的长度
空间复杂度O(M+N).

0 赞同 0 条回复

peach 普通 2023年6月19日下午9:43

思路

首先想到递归
递归终止条件：如果l1 == null 那么直接返回l2，如果l2 == null 那么直接返回 l1
单层递归逻辑：
- 单层递归，其实就是比较这两个节点的大小，小的放到这个位置，然后next和大的继续进行递归。
- 首先注意，原来的两个链表是升序的，如果l1.val < l2.val那么说明，这个位置应该是l1，但注意，下一个位置可能是l1.next，也可能是l2，因此我们这层递归return的应该是l1，然后它的next是l1.next和l2比较的结果。
- 以上，可实现递归逻辑的代码
之后，考虑虚拟头节点
- 使用虚拟头节点，最后返回虚拟头节点的next
- 进行判断，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(l1, l2.next);
            return l2;
        }
    }
}

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

0 赞同 0 条回复

伏月三十普通 2023年6月19日下午9:39

class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode newList=new ListNode(-1);
//注意要设置一个指针！！不能把链表头节点向后移动把指针向后移动
ListNode p=newList;

    //两个链表的头指针
    ListNode head1=l1;
    ListNode head2=l2;

    //设置双指针 并把头指针赋值给p1 p2
    ListNode p1=new ListNode();
    p1=head1;
    ListNode p2=new ListNode();
    p2=head2;

    //只要有一个指针指向的为空 就停止循环  两个指针必须都不为空 才执行
    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;
    }

    if(p1!=null){
        p.next=p1;
    }

    if(p2!=null){
        p.next=p2;
    }

    return newList.next;
}

}

0 赞同 0 条回复

* 普通 2023年6月19日下午9:35

c实现
struct ListNode mergeTwoLists(struct ListNode l1, struct ListNode l2){
if(l1NULL)
return l2;
if(l2NULL)
return l1;
struct ListNode root,tail,p=l1,q=l2;
root=(struct ListNode)malloc(sizeof(struct ListNode));
root->next=NULL;
tail=root;
while(p&&q){
struct ListNode *l; if(p->valval){
l=p;
p=p->next;
}
else{
l=q;
q=q->next;
}
l->next=NULL;
tail->next=l;
tail=l;
}
if(p){
tail->next=p;
}
if(q){
tail->next=q;
}
return root->next;
}

0 赞同 0 条回复

悠若普通 2023年6月19日下午9:32

先创建一个虚拟头节点，并让一个指针指向虚拟头节点，如果list1中元素小于list2就把list1链上，否则链上list2。
时间复杂度：O(n+m)，空间复杂度：O(1)

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

0 赞同 0 条回复

Dsjh 普通 2023年6月19日下午9:28

“`c++
// c++实现
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0);

    ListNode* 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;
        }
    }
    while(l1){
        cur->next = l1;
        cur = cur->next;
        l1 = l1->next;
    }
    while(l2){
        cur->next = l2;
        cur = cur->next;
        l2 = l2->next;
    }
    return dummy->next;
}

};

0 赞同 0 条回复

Dsjh 普通 2023年6月19日下午9:28

c++ 实现

0 赞同 0 条回复

mpweixin用户普通 2023年6月19日下午9:21

java语言

  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head=new ListNode(0);
        ListNode tmp=head;
        while(l1!=null&&l2!=null){
            if(l1.val>=l2.val){
                head.next=l2;
                head=head.next;
                l2=l2.next;
                continue;
            }
            if(l1.val<l2.val){
                head.next=l1;
                head=head.next;
                l1=l1.next;
                continue;
            }
        }
        if(l1==null){
            head.next=l2;
        }
        if(l2==null){
            head.next=l1;
        }

        return tmp.next;
    }

时间复杂度为n，空间复杂度为1,。
思路：使用双指针的方式，使用一个辅助链表head，并设立条件，当l1与l2相等时，让merger=l2。逐个遍历l1与l2中的值，如果l1>=l2，则让tmp=l2，且让l2的指针和head的指针指向下一位，反之亦然。最后返回辅助链表的下一位。

0 赞同 0 条回复

雨落圆荷普通 2023年6月19日下午9:07

class Solution{
public ListNode mergeTowLists(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=l1null ?l2:l1;
return merge.next;
}
}
时间复杂度：O(n+m)
空间复杂度：O(1)

0 赞同 0 条回复

行动派小彩笔普通 2023年6月19日下午8:49

“`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* ans = new ListNode(-1);
ListNode* cur1 = l1,*cur2 = l2,*ret = ans;
while(cur1 && cur2)
{
if(cur2->val < cur1->val)
{
ret->next = cur2;
cur2 = cur2->next;
}
else
{
ret->next = cur1;
cur1 = cur1->next;
}
ret = ret->next;
}
ret->next = cur1==NULL?cur2:cur1;
return ans->next;
}
};

0 赞同 0 条回复

Ming 普通 2023年6月19日下午8:48

这里是Ming的打卡：
涉及了增删改，那我们拾起好习惯：建立虚拟头结点，将两个链表统统收入，具体每一个在代码里有注解

/**
 * 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 dummy = new ListNode(0);
        ListNode cur = dummy;
        //都不为空时才有值去判断
        while(l1 != null && l2 != null) {
            //l1值比较小的时候
            if(l1.val < l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else { //l2值比较小时候，相等是谁都无所谓
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        //判断l1或者l2是空，将cur的尾巴给非空的链表
        //好色的cur就是喜欢又长又大的
        cur.next = l1 == null ? l2 : l1;
        return dummy.next;
    }
}

1 赞同 0 条回复

mpweixin用户普通 2023年6月19日下午8:47

思想：建立一个头结点，然后设置双指针，分别遍历两个链表，较小（或等于）的元素先插入新链表；最后处理未能插入的剩余链表节点
时间复杂度：O(m+n) 空间复杂度：O(1)

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //存在链表长度0的情况
        if(l1==null && l2==null)    return null;
        if(l1==null && l2!=null)    return l2;
        if(l1!=null && l2==null)    return l1;

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

        while(p!=null){
            r.next = p;
            p = p.next;
            r = r.next;
        }
        while(q!=null){
            r.next = q;
            q = q.next;
            r = r.next;
        }

        return head.next;

    }
}

0 赞同 0 条回复

Vow the vow。普通 2023年6月19日下午8:39

比较容易错的点是保证新生成的链表最后节点为null

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode newHead = new ListNode();
        ListNode node = newHead;
        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;
        }else{
            node.next = l2;
        }
        return newHead.next;
    }
}

0 赞同 0 条回复

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

共以下 99 个回答

解题思路

代码

思路

代码

# 回答此问题取消回复

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

共以下 99 个回答

解题思路

代码

思路

代码

# 回答此问题 取消回复

# 回答此问题取消回复