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

hyjob 普通 2023年8月3日下午4:09

【合并两个排序的链表】C++

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

    }
};

0 赞同 0 条回复

mpweixin用户普通 2023年8月1日下午3:24

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* preHead=new ListNode(-1);

        ListNode* prev=preHead;
        while(l1!=nullptr&&l2!=nullptr){
            if(l1->val<=l2->val){
                prev->next=l1;
                l1=l1->next;
            }else{
                prev->next=l2;
                l2=l2->next;
            }
            prev=prev->next;
        }
        prev->next=l1==nullptr?l2:l1;
        return preHead->next;
    }
};

打卡

0 赞同 0 条回复

北荒普通 2023年7月20日下午7:47

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 辅助结点
        ListNode* l = new ListNode();
        ListNode* temp = l;

<pre><code>    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 = l1;
    }

    if(l2 != nullptr){
        temp->next = l2;
    }

    return l->next;

}
</code></pre>

};

时间复杂度O(n)都要遍历一遍
空间复杂度O(1)，没有开辟了新的空间，仅仅是创建了新的结点

0 赞同 0 条回复

夏唐普通 2023年7月17日下午3:42

打卡

# 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
        """
        merge = ListNode(0)
        temp = merge
        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 else l2 # 看最后剩下的末尾
        return merge.next # 最开始的0，不需要

0 赞同 0 条回复

Rona 普通 2023年7月16日下午6:20

双指针进行比较大小依次放入新链表，注意⚠️1: dum头节点方便链表头节点进行循环 2:新链表要一直往前移动要不就在赋值同一个node
时间复杂度：O(M+N)
空间复杂度：O(1) – 没有用新的空间

# 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:
        # dum头节点方便第一个节点进行循环
        dum = cur = 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 # node needs to be moved forward to assign value

        cur.next = l1 if l1 else l2
        return dum.next

0 赞同 0 条回复

李敏普通 2023年7月16日上午12:09

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

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

    return merge.next;
}

}
···

0 赞同 0 条回复

hi 普通 2023年7月15日上午10:59

归并排序，双指针解决，有虚拟头节点

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

        if(l1) cur -> next = l1;
        if(l2) cur -> next = l2;
//这有更简单的写法，cur -> next =(l1 != null ? l1 : l2)
        return dummy -> next;
    }
};

0 赞同 0 条回复

始料未及普通 2023年7月14日下午3:57

双指针，构造新节点不需要new 直接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;
    }
    if(l2==null){
        return l1;
    }

    ListNode head=new ListNode(0);
    ListNode cur=head;
    ListNode left=l1;
    ListNode right=l2;
    while(left!=null && right!=null){
        ListNode node=null;
        if(left.val>right.val){
            cur.next=right;
            right=right.next;
        }
        else{
            cur.next=left;
            left=left.next;
        }
        cur=cur.next;
    }
    if(left==null){
        cur.next=right;
        return head.next;
    }
    cur.next=left;
    return head.next;

}

}

0 赞同 0 条回复

wowo 普通 2023年7月14日上午6:45

递归，比较两个链表的第一个节点返回较小的一个，重新合并删除掉小节点的链表和另一个链表

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if l1 is not None and l2 is not None:
            if l1.val <= l2.val:
                head = self.mergeTwoLists(l1.next, l2)
                l1.next = head
                return l1
            else:
                head = self.mergeTwoLists(l1, l2.next)
                l2.next = head
                return l2
        elif l1 is None and l2 is not None:
            return l2
        elif l1 is not None and l2 is None:
            return l1
        else:
            return None

0 赞同 0 条回复

洪小哲普通 2023年7月12日下午10:47

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dum = new ListNode(0);
        ListNode* temp = dum;
        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;  //补齐余下的listnode
        return dum->next;
    }
};

0 赞同 0 条回复

星河普通 2023年7月12日下午3:24

/*
head指向新链表，newList负责延长链表，记得newList = newList.Next
*/
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
head := &ListNode{}
newList := head

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

if l2 != nil {
    newList.Next = l2
}
if l1 != nil {
    newList.Next = l1
}
return head.Next

}

0 赞同 0 条回复

jaho 普通 2023年7月11日下午11:09

打卡

class Solution1 {
    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;
        }
    }
}
class Solution2 {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

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

        current.next = l1 != null ? l1 : l2; 
        return dummy.next;
    }
}

0 赞同 0 条回复

望仔普通 2023年7月11日下午10:24

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    /*
        同时遍历两个链表，创建新节点，返回即可
    */
    pre := &ListNode{Val: -1}
    cur := pre

    for l1 != nil || l2 != nil {
        if l1 != nil && l2 != nil {
            if l1.Val >= l2.Val {
                pre.Next = &ListNode{Val: l2.Val}
                pre = pre.Next
                l2 = l2.Next
            } else {
                pre.Next = &ListNode{Val: l1.Val}
                pre = pre.Next
                l1 = l1.Next
            }
        } else if l1 == nil && l2 != nil {
            pre.Next = &ListNode{Val: l2.Val}
            pre = pre.Next
            l2 = l2.Next
        } else if l1 != nil && l2 == nil {
            pre.Next = &ListNode{Val: l1.Val}
            pre = pre.Next
            l1 = l1.Next
        }
    }

    return cur.Next
}

0 赞同 0 条回复

我家旺仔普通 2023年7月11日下午3:35

打卡
递归
class Solution {
public:
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;
}
}
};

0 赞同 0 条回复

👾 普通 2023年7月11日下午2:58

“`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) {
ListNode prehead = new ListNode(0);
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; } //最后有一个是为null prev.next = l1==null ? l2:l1; return prehead.next; } }

0 赞同 0 条回复

喵喵神教🐈 普通 2023年7月10日下午11:33

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # p1=l1
        # p2=l2
        ls=ListNode(0)         # ！注意定义
        p3=ls
        while l1 and l2:
            if l1.val<l2.val:
                p3.next=l1     # 直接接到l1上而不是=l1.val
                l1=l1.next     #! 注意要next
            else:
                p3.next=l2
                l2=l2.next
            p3=p3.next
        if l1:
            p3.next=l1
            return ls.next      #! next，因为ls是0
        if l2:
            p3.next=l2
            return ls.next

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

0 赞同 0 条回复

Edenms-u 普通 2023年7月10日下午10:42

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


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1 == NULL && l2 == NULL)
        return NULL;
    if(l1 == NULL || l2 == NULL)
        return l1 ? l1 : l2;
    struct ListNode s = {0, NULL};
    struct ListNode *sr = &s;

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

    sr->next = l1 ? l1 : l2;
    return s.next;
}

时间O(n)
空间O(1)
用一个新的链表把两个排序链表串在一起

0 赞同 0 条回复

momo 普通 2023年7月10日下午10:16

时间复杂度 O(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 = l1;
                l1 = l1.next;
            } else {
                p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        p.next = l1 == null? l2 : l1;
        return dummy.next;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月10日下午7:51

“`C++
\\打卡
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *p,*q,*dum;
p = l1;
q = l2;
dum = new ListNode(0);
ListNode *k = dum;
while(p && q){
if(p->val < q->val){
k->next = p;
p = p->next;
k = k->next;
}
else{
k->next = q;
q = q->next;
k = k->next;
}
}
if(p){
k->next = p;
}
else{
k->next = q;
}

    return dum->next;
}

};

“`

0 赞同 0 条回复

NullPointerException 普通 2023年7月10日下午7:43

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//可以使用归并递归也可以直接遍历
if(l1null)
{
return l2;
}
if(l2null)
{
return l1;
}
if(l1.val<=l2.val)
{
l1.next= mergeTwoLists(l1.next,l2);
return l1;
}else
{
l2.next= mergeTwoLists(l1,l2.next);
return l2;
}

0 赞同 0 条回复

周小二普通 2023年7月10日上午2:17

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //定义虚拟头节点
        ListNode result = new ListNode();
        ListNode cur = result;
        //判断两个链表头节点大小，插入结果链表中
        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;
            }
        }
        while (l1 != null) {
            cur.next = l1;
            cur = cur.next;
            l1 = l1.next;
        }
        while (l2 != null) {
            cur.next = l2;
            cur = cur.next;
            l2 = l2.next;
        }
        return result.next;
    }
}

0 赞同 0 条回复

小北普通 2023年7月9日下午11:29

”’
java
”’
时间复杂度O（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 条回复

w 普通 2023年7月9日下午9:49

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 遍历两个链表，比较大小合并。
        // 申请一个伪头节点
        ListNode dum = new ListNode(0);
        ListNode cur = dum; // 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;  // cur指向刚插入进来的节点
        }
        // 若l1 == null，直接把l2后面插入进来。否则就是l2=null了。
        // 跳出循环的条件是有一个为空了。
        cur.next = l1 != null ? l1 : l2; 
        return dum.next;  // dum是空节点，新链表的头节点是dum的后一个节点
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月9日下午5:58

打卡-代码：
#include
#include string
using namespace std;

struct ListNode{
int val
ListNode* next;
ListNode(int x): val(x); next(NULL){}
};

class Solution{
ListNode* mergeTwo(ListNode l1, ListNode l2){
ListNode* merge = new ListNode(0);
ListNode* cur = merge;

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

}

0 赞同 0 条回复

神经蛙普通 2023年7月9日下午5:31

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

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 定义变量
        ListNode headNode = new ListNode(0);
        ListNode node = headNode;

        // l1 与 l2 进行比较
        while (l1 != null && l2 != null) {
            if (l1.val > l2.val) {
                node.next = l2;
                l2 = l2.next;
            } else {
                node.next = l1;
                l1 = l1.next;
            }
            node = node.next;
        }

        // 将剩下的放到末尾
        if (l1 == null && l2 != null) {
            node.next = l2;
        }
        if (l1 != null && l2 == null) {
            node.next = l1;
        }

        return headNode.next;
    }
}

0 赞同 0 条回复

3A87 普通 2023年7月9日下午2:45

“`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* 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;
    }
    temp->next=l1?l1:l2;
    return merge->next;//merge是空结点，合并的链表头节点是merge->next
}

};

“`

0 赞同 0 条回复

Evilluu 普通 2023年7月9日下午12:56

class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dumpy = ListNode(None)
cur = dumpy
while l1 and 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 == None:
        while l2 is not None:
            cur.next = l2
            cur = cur.next
            l2=l2.next
    if l2 == None:
        while l1 is not None:
            cur.next = l1
            cur = cur.next
            l1=l1.next
    return dumpy.next

双指针比较两个链表的节点值，必定有一个先为空，再添加另一个链表的节点

0 赞同 0 条回复

finalrgy 普通 2023年7月9日上午9:39

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    virtualHead :=&ListNode{}
    newNode := virtualHead
    for {
        if l1 == nil {
            newNode.Next = l2
            break
        }
        if l2 == nil {
            newNode.Next = l1
            break
        }
        if l1.Val <= l2.Val {
            newNode.Next = l1
            l1 = l1.Next
        } else {
            newNode.Next = l2
            l2 = l2.Next
        }
        newNode = newNode.Next
    }
    return virtualHead.Next
}

思路：两个指针指向两个排序的链表，比较两个指针的节点大小，新链表的尾节点指向小的节点，指针移动，一直比较
时间复杂度O(N) 空间复杂度O(1)

0 赞同 0 条回复

刹那芳间普通 2023年7月9日上午7:36

/**
  构建两个node，一个是头节点，一个是临时节点，用于拼接新链表节点
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //特殊情况
        if(l1==null && l2==null){
            return null;
        }
        ListNode node = new ListNode(0);
        ListNode temp = node;
        while(l1!=null && l2!=null){
            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(l1 != null){
            temp.next = l1;
        }
        if(l2 != null){
            temp.next = l2;
        }
        return node.next;
    }
}

0 赞同 0 条回复

新禾普通 2023年7月9日上午1:11

递归
时间复杂度：O(n+m)
空间复杂度：O(n+m)
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 null){
return l2;
} else if(l2 null) {
return l1;
}

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

}

0 赞同 0 条回复

人生何处不青山普通 2023年7月8日下午11:35

估计也就我用TS了

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    let a = l1, b = l2;
    let newHead = new ListNode(0);
    let res = newHead;
    while (a && b) {
        if (a.val < b.val) {
            newHead.next = a;
            a = a.next;
        } else {
            newHead.next = b;
            b = b.next;
        }
        newHead = newHead.next;
    }
    while (a) {
        newHead.next = a;
        a = a.next;
        newHead = newHead.next;
    }
    while (b) {
        newHead.next = b;
        b = b.next;
        newHead = newHead.next;
    }
    return res.next;
};

0 赞同 0 条回复

ㅤ 普通 2023年7月8日下午11:20

/**
     * 剑指 Offer 25. 合并两个排序的链表
     * https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/
     * 思路：构建两个Node，一个root，头节点为空节点，另一个temp临时节点，用于拼接有序链表。
     *      1、按链表的大小，将链表节点组装到temp节点中
     *      2、可能存在一条链表较另一条短些，将长的链条剩余部分全部拼装在temp之后
     *      3、直接返回 root.next
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 特殊情况
        if (l1 == null && l2 == null) {
            return null;
        }
        ListNode root = new ListNode(-1);
        ListNode temp = root;
        // 先按照顺序构建链表
        while (l1 != null && l2 != null) {
            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;
        }
        // 可能存在有一条链表为空，则将另一条链表直接放在temp链表之后
        if (l1 == null) {
            temp.next = l2;
        } else {
            temp.next = l1;
        }
        return root.next;
    }

0 赞同 0 条回复

富城普通 2023年7月8日下午10:01

第一天第三题

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


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


    }
}

0 赞同 0 条回复

V2ero 普通 2023年7月8日下午9:33

代码如下

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummy = new ListNode();
    let cur = dummy;
    while(l1 && l2){
        if(l1.val > l2.val){
            cur.next = l2;
            l2 = l2.next
        } else {
            cur.next = l1;
            l1 = l1.next
        }
        cur = cur.next
    }
    if(l1){
        cur.next = l1;
    }
    if(l2){
        cur.next = l2;
    }
    return dummy.next
};

0 赞同 0 条回复

Rico 普通 2023年7月8日下午9:32

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        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==NULL ? l2 : l1;

        return merge->next;

    }
};

0 赞同 0 条回复

CKX 普通 2023年7月8日下午9:06

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    //新节点
    head := &ListNode{}
    temp := head

    //l1和l2逐个元素比较，有序的插入到新链表中
    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            temp.Next = l1
            l1 = l1.Next
        } else {
            temp.Next = l2
            l2 = l2.Next
        }
        temp = temp.Next
    }

    //将不为空的剩余链表直接接到链表尾部
    if l2 != nil {
        temp.Next = l2
    } else {
        temp.Next = l1
    }
    return head.Next
}

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

0 赞同 0 条回复

#00456B 普通 2023年7月8日下午8:37

设置一个虚拟头节点，用来记录新的链表。首先按照两个链表的较小长度来进行排序添加到新链表。然后通过判断l1是否已经遍历完毕从而选择连接新链表后面的是l1还是l2。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* left = l1;
        ListNode* right = l2;
        ListNode* dummyHead = new ListNode();
        ListNode* cur = dummyHead;
        while(left && right){
            if(left->val <= right->val){
                cur->next = left;
                left = left->next;
            }
            else{
                cur->next = right;
                right = right->next;
            }
            cur = cur->next;
        }
        cur->next = (left != NULL) ? left:right;
        return dummyHead->next;
    }
};

0 赞同 0 条回复

普通 2023年7月8日下午8:30

c++代码
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

          ListNode* Pre=new ListNode(1);
          ListNode* Cur=Pre;
          while(l1&&l2)
          {
              if(l1->val<l2->val)
              Pre->next=l1,l1=l1->next,Pre=Pre->next;
              else
                Pre->next=l2,l2=l2->next,Pre=Pre->next;
          }
          Pre->next=l1==NULL?l2:l1;
          return Cur->next;
}

};

0 赞同 0 条回复

坏掉的世界永久会员 2023年7月8日下午8:24

代码

/**
 * 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&&!l2){
            return NULL;
        }
        auto dummy = new ListNode(-1);
        auto p = dummy;
        while(l1&&l2){
            if(l1 -> val <= l2 -> val){
                p -> next = l1;
                l1 = l1 -> next;

            }else{
                p -> next = l2;
                l2 = l2 -> next;
            }
            p = p -> next;
        }
        if(l1){
            p -> next =l1;
        }
        if(l2){
            p -> next = l2;
        }
        return dummy -> next;

    }
};

0 赞同 0 条回复

土豆芋泥包_ 普通 2023年7月8日下午8:03

代码

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

mpweixin用户永久会员 2023年7月8日下午7:32

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

时间复杂度 O(m+n)

0 赞同 0 条回复

Fighting boy😀 普通 2023年7月8日下午6:24

//C++实现
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
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年7月8日下午5:47

双指针按顺序拼接。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* newhead=new ListNode(-1);
        ListNode* cur;
        cur=newhead;
        while(l1!=NULL || l2!=NULL){
            if(l1 == NULL){
             cur->next=new ListNode(l2->val);
             cur=cur->next;
             l2=l2->next;
            }
            else if(l2 == NULL){
             cur->next=new ListNode(l1->val);
             l1=l1->next;
             cur=cur->next;
            }
            else{
                if(l1->val > l2->val){
                    cur->next=new ListNode(l2->val);
                    cur=cur->next;
                    l2=l2->next;
                }
                else{
                  cur->next=new ListNode(l1->val);
                    cur=cur->next;
                    l1=l1->next;
                }
            }

        }



        return newhead->next;

    }
};

0 赞同 0 条回复

Ad. 普通 2023年7月8日下午5:35

这题展现了一个新链表的拼接过程，即按序拼接。
思路上，还是用到了双指针，分别维护两个链表。具体如下：
1. 定义合并的链表
2. 节点拼接，将两个指针指向的元素进行比较，小的优先拼接。
3. 当退出循环时，会存在某一个链表的最后一个节点没有拼接上，则需要额外进行判断。不为空的链表，需要进行节点的添加。

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

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

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

0 赞同 0 条回复

ppopp 普通 2023年7月8日下午5:27

ˋˋˋ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 *head = new ListNode(-1); //初始化一个新的节点,括号内的值为初始，可为任意值
//head节点内值不动，它和pre值是一样的，也就是这个链表头节点是确定的
ListNode *pre = head;
while(l1 != nullptr && l2 != nullptr) {
if(l1->val > l2->val){
pre->next = l2;
l2 = l2->next;
}else{
pre->next = l1;
l1 = l1->next;
}
pre = pre->next;
}
pre->next = (l1 nullptr ? l2:l1);
return head->next;
}
};
ˋˋˋ

0 赞同 0 条回复

小季同学普通 2023年7月8日下午4:53

迭代，创建虚拟节点，创建当前指针指向虚拟节点，然后对值进行判断，再加入新链表即可

function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    // 创建虚拟节点
    let dummy = new ListNode(-1)
    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
        }
        cur.next = l1 === null ? l2 : l1
    return dummy.next
};

0 赞同 0 条回复

offer收割机普通 2023年7月8日下午3:59

打卡剑指 Offer 25. 合并两个排序的链表

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 辅助节点
        ListNode newNode = new ListNode();
        // 返回的链表
        ListNode res = newNode;
        // 同时遍历两个链表，都不为空
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val){
                newNode.next = l1;
                l1 = l1.next;
                newNode = newNode.next;
            }else {
                newNode.next = l2;
                l2 = l2.next;
                newNode = newNode.next;
            }
        }
        if (l1 == null){
            newNode.next = l2;
        }
        if (l2 == null){
            newNode.next = l1;
        }
        return res.next;               
    }
}

0 赞同 0 条回复

mpweixin用户普通 2023年7月8日下午3:12

class Solution {
    // 输入：1->2->4, 1->3->4
    //输出：1->1->2->3->4->4
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummpy = new ListNode(-1);
        ListNode cur = new ListNode(-1);
        dummpy = cur;
        while (l1!=null && l2!=null) {
            if (l1.val <= l2.val) {
                //ListNode ln = new ListNode(l1.val);
                cur.next = l1;
                cur = l1;
                l1 = l1.next;
            } else {
                //ListNode ln = new ListNode(l2.val);
                cur.next = l2;
                cur = l2;
                l2 = l2.next;
            }
        }
        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null) {
            cur.next = l2;
        }
        return dummpy.next;
    }
}

0 赞同 0 条回复

片言莫语普通 2023年7月8日下午2:34

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) { // 定义一个公有的mergeTwoLists方法，传入两个ListNode（链表）类型参数l1和l2。
        ListNode dum = new ListNode(0);  // 建立一个新的头结点，这样可以统一处理所有的元素（包括原来的头结点），避免特殊处理。
        ListNode cur = dum;  // 创建当前节点cur并初始化指向dum，cur将以后移动来跟踪新链表的尾部。

        while(l1 != null && l2 != null){  // 当两个链表都不为空时，进入循环。
            if(l1.val < l2.val){  // 如果l1链表当前节点值小于l2链表当前节点值。
                cur.next = l1;  // 将cur的next指针指向l1，将l1添加到新链表的尾部。
                l1 = l1.next;   // l1指针后移。
                cur = cur.next; // 移动cur指针，保持其指向新链表的最后一个节点。
            }else{  // 如果l2链表当前节点值小于等于l1链表当前节点值。
                cur.next = l2;  // 将cur的next指针指向l2，将l2添加到新链表的尾部。
                l2 = l2.next;   // l2指针后移。
                cur = cur.next; // 移动cur指针，保持其指向新链表的最后一个节点。
            }
        }
        cur.next = l1 != null ? l1 : l2; // 若有一个链表遍历完毕，直接将另一个链表剩余部分添加到新链表的尾部。

        return dum.next; // 返回新链表的头结点的下一个节点，即新链表的真正头部节点，因为dum是我们自己添加的哑巴节点。
    }
}

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

0 赞同 0 条回复

KCOcean 普通 2023年7月8日下午1:23

代码

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        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 条回复

艺普通 2023年7月8日下午1:16

“`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 *merg = new ListNode(0);
ListNode *temp=merg;
while(l1!=NULL&&l2!=NULL)
{
if(l1->valval)
{
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 merg->next;
}
};
//时间复杂度：O(n+m)
//空间复杂度：O(n+m）

0 赞同 0 条回复

H、普通 2023年7月8日下午1:04

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

        if(l1 == null){
            return  l2;
        }

        if(l2 == null){
            return  l1;
        }

        ListNode mergeL = new ListNode(0);

        ListNode tempL = mergeL;


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

        }

        if(l1 != null){
            tempL.next = l1;
        }

        if(l2 != null){
            tempL.next = l2;
        }

        return mergeL.next;

    }
}

0 赞同 0 条回复

枫梓。普通 2023年7月8日下午12:57

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* pre = dummy;
        ListNode* cur;
        while(list1!=nullptr && list2!= nullptr){
            if(list1->val < list2->val) {
                pre->next = list1;
                list1 = list1->next;
            } else {
                pre->next = list2;
                list2 = list2->next;
            }
            pre = pre->next;
        }
        if(list1 == nullptr){
            pre->next=list2;
        }else{
            pre->next=list1;
        }
        return dummy->next;
    }
};

合并两个有序链表

0 赞同 0 条回复

mpweixin用户普通 2023年7月8日下午12:50

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) {
ListNode s = new ListNode(0);//辅助节点
ListNode p = s;
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 s.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;
}
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 条回复

爱吃胡萝卜🥕的兔子🐰 普通 2023年7月8日下午12:40

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1 == nil{
        return l2
    }
    if l2 == nil{
        return l1
    }

    dummy := &ListNode{}
    cur := dummy
    for l1 != nil && l2 != nil{
        if l1.Val < l2.Val{
            cur.Next = l1
            l1 = l1.Next
        }else{
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }

    if l1 != nil{
        cur.Next = l1
    }

    if l2 !=nil{
        cur.Next = l2
    }
    return dummy.Next

}

打卡

0 赞同 0 条回复

Mooby 普通 2023年7月8日上午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) {
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 条回复

mpweixin用户普通 2023年7月8日上午11:26

public Node mergeNode(Node head1,Node head2){
Node phead=new Node(0);
Node head =phead;
while (head1!=null && head2!= null) {
if (head1.data <= head2.data) {
head.next= head1;
head1 = head1.next;
head=head.next;
}
else {
head.next=head2;
head2=head2.next;
head=head.next;
}
}
if (head1null)head.next=head2;
if (head2null)head.next=head1;

    return phead.next;
}

时间复杂度 O(N)
空间复杂度O（n）

0 赞同 0 条回复

波雅汉库克普通 2023年7月8日上午3:54

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

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

0 赞同 0 条回复

长河呼叫黄江普通 2023年7月8日上午12:29

Day1：下面是代码
#方法1 递归

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

#方法2 伪头节点


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

1 赞同 0 条回复

旺旺旺普通 2023年7月8日上午12:29

以下是代码

# 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
        """
        merge=ListNode(0)
        temp=merge

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

        temp.next=l1 if l1 else l2
        return merge.next

0 赞同 0 条回复

June 普通 2023年7月8日上午12:25

/**
 * 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 p1;
        ListNode p2;
        if(l1.val < l2.val)
        {
            p1 = l1;
            p2 = l2;
        }
        else
        {
            p1 = l2;
            p2 = l1;
        }
        ListNode ans = p1;
        // 把 p2 合并到 p1
        while(p1.next != null && p2 != null)
        {

            if(p2.val >= p1.val && p2.val < p1.next.val)
            {
                ListNode p2next = p2.next;
                p2.next = p1.next;
                p1.next = p2;
                p2 = p2next;
            }
            p1 = p1.next;
        }

        if(p1.next == null)
        {
            p1.next = p2;
        }


        return ans;
    }
}

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

0 赞同 0 条回复

是非之欢普通 2023年7月8日上午12:11

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

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

0 赞同 0 条回复

醒醒醒醒普通 2023年7月8日上午12:10

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

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

1..定义一个新链表和辅助链表，新链表赋值给辅助链表，对两个链表的值进行排序，存储在辅助链表，最后返回新链表。
2.O（n+m），O（1）

0 赞同 0 条回复

momo 普通 2023年7月7日下午11:42

定义一个头节点，头结点指向一个较小的链表的头，遍历两个链表，将较小的一端加入到头结点的下一个节点，继续，知道有一条链表为空，并将不为空的链表全部插入到末尾。

struct ListNode {
    int val;
    struct ListNode *next;
};

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

    while(l1){
        temp->next = l1;
        temp = temp->next;
        l1 = l1->next;
    }
    while (l2)
    {
        temp->next = l2;
        temp = temp->next;
        l2 = l2->next;
    }

    return head;
}

0 赞同 0 条回复

Luminous 普通 2023年7月7日下午11:26

/**
 * 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 newHead=new ListNode(0);
        ListNode cur=newHead;
        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 newHead.next;
    }
}

时间复杂度：O(m+n),其中m和n分别为两个链表中的长度
空间复杂度：O(1)

0 赞同 0 条回复

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

/**
 * 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 preHead = new ListNode(-1);
        ListNode pre = preHead;
        // 直接使用原节点
        while(l1!=null&&l2!=null){
            if(l1.val<=l2.val){
                // 构造新链表,选择比较中较小的作为next
                pre.next = l1;
                l1 = l1.next;
            } else{
                pre.next = l2;
                l2 = l2.next;
            }
            pre = pre.next;
        }
        // 有一条已经比完，将另一条链接上去
        pre.next = l1==null?l2:l1;
        // 真正的头节点
        return preHead.next;
    }
}

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

0 赞同 0 条回复

mpweixin用户普通 2023年7月7日下午11:13

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

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

0 赞同 0 条回复

阿尚普通 2023年7月7日下午11:12

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

    ListNode dummy = new ListNode(0);//虚拟节点

    ListNode pre = dummy;

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

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

    return dummy.next;
}

}

0 赞同 0 条回复

朱志刚普通 2023年7月7日下午11:05

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

}

};
执行用时：
12 ms
,内存消耗：
18.7 MB
,

0 赞同 0 条回复

@ 李小二普通 2023年7月7日下午10:57

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 null) {
return l2; // 如果 l1 为空，返回 l2
}

if (l2 == null) {
    return l1; // 如果 l2 为空，返回 l1
}

if (l1.val < l2.val) { // 比较两个链表当前节点的值

    l1.next = mergeTwoLists(l1.next, l2); // 将较小的节点的 next 指针指向递归调用的结果
    return l1; // 返回较小节点作为合并后链表的头节点

} else {

    l2.next = mergeTwoLists(l1, l2.next); // 将较小的节点的 next 指针指向递归调用的结果
    return l2; // 返回较小节点作为合并后链表的头节点

}

}

0 赞同 0 条回复

Terence💧 普通 2023年7月7日下午10:42

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    ret := &ListNode{}
    p := ret
    for l1 != nil && l2 != nil {
        if l1.Val < l2.Val {
            p.Next = l1
            l1 = l1.Next
        }else {
            p.Next = l2
            l2 = l2.Next
        }
        p = p.Next
    }

    if l1 != nil {
        p.Next = l1
    }

    if l2 != nil {
        p.Next = l2
    }

    return ret.Next
}

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

0 赞同 0 条回复

北辰普通 2023年7月7日下午10:16

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（m+n）
空间复杂度：O（m+n）
思路：递归解法。
if l1.val<l2.val:
l1 + merger(l1[1:],l2)
else:
l2+merger(l1,l2[1:])

0 赞同 0 条回复

ONE PIECE 普通 2023年7月7日下午9:28

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

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

0 赞同 0 条回复

桎梏普通 2023年7月7日下午9: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(-1);
        ListNode pre = head;
        while(l1 != null && l2 != null) {
            if(l1.val > l2.val) {
                head.next = l2;
                head = head.next;
                l2 = l2.next;
            }else {
                head.next = l1;
                head = head.next;
                l1 = l1.next;
            }
        }
        if(l1 != null) {
            head.next = l1;
        }else {
            head.next = l2;
        }
        return pre.next;
    }
}

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

0 赞同 0 条回复

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

共以下 74 个回答

打卡剑指 Offer 25. 合并两个排序的链表

# 回答此问题取消回复

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

共以下 74 个回答

打卡 剑指 Offer 25. 合并两个排序的链表

# 回答此问题 取消回复

打卡剑指 Offer 25. 合并两个排序的链表

# 回答此问题取消回复