mpweixin用户普通 2024年3月28日下午10:15

python
class Solution(object):
def trainningPlan(self, l1, l2):
“””
:type l1: Optional[ListNode]
:type l2: Optional[ListNode]
:rtype: Optional[ListNode]
“””
if not l1:
return l2
if not l2:
return l1

    if l1.val < l2.val:
        l1.next = self.trainningPlan(l1.next, l2)
        return l1
    else:
        l2.next = self.trainningPlan(l1, l2.next)
        return l2

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

0 赞同 0 条回复

晚睡晚起起不来永久会员 2024年3月28日下午1:56

java
思路
首先初始化
1.memger 创建辅助节点
2.temp指向memger

接下来进行循环对比l1和l2，把较小的值放入temp中
然后temp往后继续遍历

退出循环后，查看遍历完成的是哪个，把未遍历完成的放入合并后的链表里 temp.next

// 你的 Java 代码写在这里
class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
//初始化memger 创建一个辅助节点
        ListNode memger = new ListNode(0);
//初始化temp临时节点
        ListNode temp = memger;
//while循环 为空退出循环
        while(l1 !=null && l2 != null){
//对l1 l2 进行比较
            if(l1.val < l2.val){
//把小的值放入新的链表中
                temp.next = l1;
//l1往后移动
                l1 = l1.next;
            }else{
                temp.next = l2;
                l2 = l2.next;
            }
//temp往后移动继续遍历，直到末尾退出循环
            temp = temp.next;
        }
//新链表判断l1是否到达末尾，如果是，就把l2接入，如果不是就把l1接入
        temp.next = l1 == null ? l2 : l1;
//最后返回memger的下一个节点 真正的头节点
        return memger.next;
    }
}

作者：I2ecursing McclintockMct
链接：https://leetcode.cn/problems/he-bing-liang-ge-pai-xu-de-lian-biao-lcof/solutions/2712298/lcr-142-xun-lian-ji-hua-iv-by-i2ecursing-wvuu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

0 赞同 0 条回复

熊猫不是猫普通 2024年3月26日下午12:00

“`c++
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode *merger = new ListNode(0);
ListNode *temp = merger;

    while(list1 != nullptr && list2 != nullptr) {
        if (list1->val <= list2->val) {
            temp->next =list1;
            list1 = list1 ->next;
        } else {
            temp->next =list2;
            list2 = list2->next;
        }
        temp = temp->next;
    }

    temp->next = list2 ? list2 :list1;
    return merger->next;
}

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

“`

0 赞同 0 条回复

钱大牙普通 2024年3月25日下午10:54

时间复杂度：O(n+m)，n 和 m 表示两个链表长度
空间复杂度：O(1)
class Solution:
def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
res = ListNode(0)
tmp = res
while l1 and l2:
if l1.val < l2.val:
tmp.next = l1
l1 = l1.next
else:
tmp.next = l2
l2 = l2.next
tmp = tmp.next
if l1:
tmp.next = l1
else:
tmp.next = l2
return res.next

0 赞同 0 条回复

山月普通 2024年3月13日下午10:32

//合并两个链表，我的思路过于混乱了
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode trainningPlan(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode(0);
ListNode* cur = head;
while(l1 && l2)
{
if(l1->val < l2->val)
{
cur->next = l1;
l1 = l1->next;
}
else
{
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}

if (l1) cur->next = l1;
else cur->next = l2;
return head->next;


}

};

0 赞同 0 条回复

RunAsOne 普通 2024年3月11日下午4:18

第三次打卡

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def trainningPlan(self, l1, l2):
        """
        :type l1: Optional[ListNode]
        :type l2: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        prehead = ListNode(0)
        prev = prehead
        while l1 and l2:
            if l1.val < l2.val:
                prev.next = l1
                l1 = l1.next
            else:
                prev.next = l2
                l2 = l2.next
            prev = prev.next
        if l1:
            prev.next = l1
        else:
            prev.next = l2
        return prehead.next

0 赞同 0 条回复

雨落星空普通 2024年3月9日下午8:46

时间复杂度：O(m+n) 空间复杂度：O（1）
”’python
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 条回复

Eugene 普通 2024年3月6日下午1:13

Definition for singly-linked list.

class ListNode(object):

def init(self, val=0, next=None):

self.val = val

self.next = next

class Solution(object):
def trainningPlan(self, l1, l2):
“””
:type l1: Optional[ListNode]
:type l2: Optional[ListNode]
:rtype: Optional[ListNode]
“””
tmp = ListNode(-1)
result = tmp
while l1 and l2:
if l1.val >= l2.val:
result.next = l2
l2 = l2.next
else:
result.next = l1
l1 = l1.next
result = result.next

    result.next = l1 if l1 else l2
    return tmp.next

提交

0 赞同 0 条回复

🌈 普通 2024年3月5日下午10:46

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode trainningPlan(ListNode* l1, ListNode* l2) {
ListNode* dummy = new ListNode(0,nullptr);
ListNode* cur = dummy;
while(l1!=nullptr && l2!=nullptr){
if(l1->val > l2->val){
cur->next = l2;
l2 = l2->next;
}else{
cur->next = l1;
l1 = l1->next;
}
cur = cur->next;
}
cur->next = l1 nullptr ? l2 : l1;
return dummy->next;
}
};

l1和l2不能同时后移一个节点

0 赞同 0 条回复

e=mc² 普通 2024年3月5日上午11:08

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        ListNode result = new ListNode();
        // 设置和result一样的链表操作拼接
        ListNode temp = result;
        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 result.next;
    }
}

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

0 赞同 0 条回复

LAVI 普通 2024年3月5日上午10:47

class Solution {
public ListNode trainningPlan(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 条回复

C C 普通 2024年3月5日上午7:34

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[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
#时间复杂度 O(n+m)
#空间复杂度 O(1)

0 赞同 0 条回复

时生普通 2024年3月4日下午9:27

//双指针遍历两个链表，值小的加入新链表，并更新l1 和 l2的指针向后移动
struct ListNode* trainningPlan(struct ListNode* l1, struct ListNode* l2) {
typedef struct ListNode ListNode;
ListNode *headNode = malloc(sizeof(ListNode));
headNode->next = NULL;
ListNode *p = headNode;
ListNode *r1;
ListNode *r2;
while(l1!=NULL && l2!=NULL){
if(l1->val <= l2->val){
r1 = l1->next;
l1->next = p->next;
p->next = l1;
p = p->next;
l1 = r1;
}else{
r2 = l2->next;
l2->next = p->next;
p->next = l2;
p = p->next;
l2 = r2;
}
}
if(l1!=NULL){
p->next = l1;
}
if(l2!=NULL){
p->next = l2;
}
return headNode->next;
}

0 赞同 0 条回复

mpweixin用户普通 2024年3月4日下午5:08

public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);
ListNode prev = prehead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
prev.next = l1 null ? l2 : l1;
return prehead.next;
}
思路：遍历合并，没合并完的直接拼接
时间O(n),空间O(n)
题解还可以用递归来解

0 赞同 0 条回复

Yeah~ 普通 2024年3月4日下午4:07

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode trainningPlan(ListNode* l1, ListNode* l2) {
if(l1 nullptr) return l2;
if(l2 nullptr) return l1;
ListNode* ret = new ListNode;
ListNode* tmp = ret;
ListNode* first = l1;
ListNode* second = l2;

    while(first != nullptr && second != nullptr){
        if(first->val < second->val){
            tmp->next = first;
            tmp = tmp->next;
            first = first->next;
        }else{
        tmp->next = second;
        tmp = tmp->next;
        second = second->next;
        }
    }
    if(first == nullptr){
        tmp->next = second;
        tmp = tmp->next;
    }else{
        tmp->next = first;
        tmp = tmp->next;
    }

    return ret->next;
}

};

一般方法，观察评论区写法，最后几行可以用三元表达式替换

0 赞同 0 条回复

阿野普通 2024年3月4日下午3:05

#双指针
var trainningPlan = function(l1, l2) {
let node1 = l1;
let node2 = l2;
let res = new ListNode(0);
let p = res;
while(node1 && node2){
if(node1.val > node2.val){
p.next = node2;
node2 = node2.next;
}else{
p.next = node1;
node1 = node1.next;
}
p = p.next;
}
p.next = node1?node1:node2;
return res.next;
};

0 赞同 0 条回复

湘江小水鬼普通 2024年3月4日下午2:58

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode next;
* };
*/
struct ListNode trainningPlan(struct ListNode* l1, struct ListNode* l2) {
if (!l1) {
return l2;
}
if (!l2) {
return l1;
}
struct ListNode* merge = NULL;
if(l1->val < l2->val){
merge = l1;
merge->next = trainningPlan(l1->next,l2);
}
else{
merge = l2;
merge->next = trainningPlan(l1,l2->next);
}
return merge;
}采用递归的方式进行的求解，空间复杂度为O(n+M)

0 赞同 0 条回复

小玉普通 2024年3月4日下午1:05

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
自己想的笨办法
struct ListNode* trainningPlan(struct ListNode* l1, struct ListNode* l2) {
    typedef struct ListNode Node;
    Node* p = (Node*)malloc(sizeof(Node));
    Node* H = (Node*)malloc(sizeof(Node));
    H = p;
    if (l1 == NULL)
        return l2;
    if (l2 == NULL)
        return l1;
    while (l1 != NULL || l2 != NULL) {
        if (l1->val < l2->val) {
            Node* q = (Node*)malloc(sizeof(Node));
            q->next = NULL;
            q->val = l1->val;
            p->next = q;
            p = q;
            l1 = l1->next;
        } else {
            Node* q = (Node*)malloc(sizeof(Node));
            q->next = NULL;
            q->val = l2->val;
            p->next = q;
            p = q;
            l2 = l2->next;
        }
        if (l1 == NULL) {
            Node* q = (Node*)malloc(sizeof(Node));
            q = H;
            while (q->next != NULL)
                q = q->next;
            q->next = l2;
            return H->next;
        }
        if (l2 == NULL) {
            Node* q = (Node*)malloc(sizeof(Node));
            q = H;
            while (q->next != NULL)
                q = q->next;
            q->next = l1;
            return H->next;
        }
    }
    return NULL;
}

0 赞同 0 条回复

YOLO 普通 2024年3月4日下午12:08

class Solution {
public:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
ListNode* merge = new ListNode(0);
ListNode* temp = merge;

    while(l1 != nullptr && l2 != nullptr){
        if(l1->val > l2->val){
            temp->next = l2;
            l2 = l2->next;
        }
        else{
            temp->next = l1;
            l1 =l1->next;
        }
        temp = temp->next;
    }
    if(l1 == nullptr){
        temp->next = l2;
    }
    if(l2 == nullptr){
        temp->next = l1;
    }
return merge->next;

}

};

0 赞同 0 条回复

Thaddeus 永久会员 2024年3月4日上午10:59

打卡

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

0 赞同 0 条回复

一个达不刘普通 2024年3月4日上午8:44

设置新头结点，分别遍历l1 l2, 途中比较大小，顺序链接在新头结点上。最后返回新头结点的下一节点——即所求新链表。
class Solution {
public:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
ListNode *dum = new ListNode(0);
ListNode *cur = dum;
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;
}
if(l1!=nullptr){
cur->next = l1;
}else{
cur->next = l2;
}
return dum->next;

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

0 赞同 0 条回复

繁星普通 2024年3月3日下午10:33

class Solution {
//时间复杂度O(n)，空间复杂度O(1)
public ListNode trainningPlan(ListNode l1, ListNode l2) {
//先将特殊情况处理
ListNode newHead = null;
if(l1 null && l2 null) return newHead;
if(l1 null) return l2;
if(l2 null) return l1;
//比较大小，小的往新链表上加
newHead = new ListNode();
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;
}
//其中一条链表已经走完，将另一条拼上
if(l1 null) cur.next = l2;
if(l2 null) cur.next = l1;
return newHead.next;
}
}

0 赞同 0 条回复

东普通 2024年3月3日下午9:26

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0), cur = pre;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
}
else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2;
return pre.next;
}
}
时间复杂度 O(M+N)
空间复杂度 O(1)

0 赞同 0 条回复

=.= 普通 2024年3月3日下午7:35

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode res = new ListNode(-1);

    ListNode p1 = l1;
    ListNode p2 = l2;
    ListNode cur = res;

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

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

    return res.next;
}

}

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

0 赞同 0 条回复

一颗红豆普通 2024年3月3日下午4:36

时间复杂度o（n），空间复杂度o（1）
合并两个有序链表，两个链表从头开始遍历，将较小值放入merge链表即可，并将放入的节点改为下一节点
技巧是空节点的辅助，不用每次都判空
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode trainningPlan(ListNode* l1, ListNode* l2) {
ListNode *merge = new ListNode(0);
ListNode *temp = merge;
while(l1!=nullptr&&l2!=nullptr)
{
if(l1->valval)
{
temp->next = l1;
l1 = l1->next;
}
else
{
temp->next = l2;
l2 = l2->next;
}
temp = temp->next;
}
temp->next = l1nullptr? l2:l1;
return merge->next;

};

0 赞同 0 条回复

一期一会普通 2024年3月3日下午3:31

递归调用函数
时间复杂度为O(M+N),空间复杂度为O(1)

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

    }
};

0 赞同 0 条回复

刘超波普通 2024年3月2日下午10:18

打卡/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode d1 = l1;
ListNode d2 = l2;
ListNode ret = new ListNode();
ListNode r = ret;
while (d1!=null&&d2!=null)
{
if (d1.val<d2.val)
{
r.next = d1;
r = r.next;
d1 = d1.next;
}else{
r.next = d2;
r = r.next;
d2 = d2.next;
}
}

    while (d1!=null)
    {
        r.next = d1;
            r = r.next;
            d1 = d1.next;
    }
    while (d2!=null)
    {
          r.next = d2;
            r = r.next;
            d2 = d2.next;
    }

    return ret.next;

}

}

0 赞同 0 条回复

mpweixin用户普通 2024年3月2日下午10:12

java
class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode dum = new listNode(0), cur = dum;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 != null ? l1:l2;
return dum.next;
}
}
提交

0 赞同 0 条回复

晚风、普通 2024年3月2日下午9:40

class Solution:
def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
new_l = dum = ListNode(0)
#res 都记录在l1中
while l1 and l2:
if l1.val < l2.val:
new_l.next = l1
l1 = l1.next
else:
new_l.next = l2
l2 = l2.next
new_l = new_l.next
new_l.next = l1 if l1 else l2
return dum.next
思路：
1.初始化一个链表作为结果
2.while循环，只要链表1或者链表2有一个为none,则跳出循环
链表1和链表2此时的node的值的大小，谁小放在新的链表中，
3.将链表剩下的部分，拼接到新的链表上
时间复杂度：o(n)
空间复杂度：o(1)

0 赞同 0 条回复

小耿普通 2024年3月2日下午9:12

”’C++
class Solution {
public:
ListNode* trainingPlan(ListNode* head, int cnt) {
// if(head nullptr) return head;
ListNode* p = head;
for(int i=0; i<cnt; i++){
// if(p nullptr) {
// return nullptr; // 一共都没有cnt个
// }
p = p->next; // 这一行要放到下面
}
ListNode* slow = head;
while(p != nullptr) {
slow = slow->next;
p = p->next;
}

    return slow;
}

};

0 赞同 0 条回复

Augenstern 普通 2024年3月2日下午8:02

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

}

1 赞同 0 条回复

mpweixin用户普通 2024年3月2日下午7:01

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        ListNode pre = root;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                pre.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                pre.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            pre = pre.next;
        }
        if (l1 != null) {
            pre.next = l1;
        }
        if (l2 != null) {
            pre.next = l2;
        }

        return root.next;
    }
}

时间复杂度O(n)

0 赞同 0 条回复

恭喜发财💰 普通 2024年3月2日下午6:56

”’java
// 代码
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode listNode=new ListNode(0);
ListNode temp=listNode;
while(l1!=null&&l2!=null){
if(l1.val>l2.val){
listNode.next=l2;
l2=l2.next;
}else{
listNode.next=l1;
l1=l1.next;
}
listNode=listNode.next;
}
listNode.next=l1!=null?l1:l2;
return temp.next;
}

0 赞同 0 条回复

零普通 2024年3月2日下午6:50

思路：遍历比较两个列表，小的插入结果，复杂度：O(n)
代码：

“`java

public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode node = result;
while (null != l1 && null != l2) {
if (l1.val >= l2.val) {
node.next = l2;
node = node.next;
l2 = l2.next;
}else {
node.next = l1;
node = node.next;
l1 = l1.next;
}
}
if (null != l1) {
node.next = l1;
}
if(null != l2) {
node.next = l2;
}
return result.next;
}

0 赞同 0 条回复

哆啦A梦的面包普通 2024年3月2日下午6:00

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func trainningPlan(l1 *ListNode, l2 *ListNode) *ListNode {
    if l1==nil{   //递归终止条件
        return l2
    } 
    if l2==nil{    //递归终止条件
        return l1 
    }
    if l1.Val>l2.Val{  //交换两节点
        l1,l2=l2,l1
    }
    l1.Next=mergeTwoLists(l1.Next,l2)  //递归
    return l1
}

0 赞同 0 条回复

Jankin 普通 2024年3月2日下午5:49

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(0);
        ListNode temp = head;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                temp.next = list1;
                list1 = list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        temp.next = list1 == null ? list2 : list1;
        return head.next;
    }
}

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

0 赞同 0 条回复

莫～慢～待普通 2024年3月2日下午5:26

class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode virtualnode=new ListNode(-1);
ListNode node=virtualnode;
while((list1!=null)&&(list2!=null))
{
int val=list1.val>list2.val?list2.val:list1.val;
if(vallist1.val)
list1=list1.next;
else
list2=list2.next;
node.next=new ListNode(val);
node=node.next;
}
if(list1!=null)
node.next=list1;
else
node.next=list2;
return virtualnode.next;
}
}
时间复杂度O(M+N)
空间复杂度O(1)

0 赞同 0 条回复

demon 普通 2024年3月2日下午5:10

创建哨兵位的头结点，不存储有效数据，并用head和tail指针指向头节点，两个有序链表从头结点位置开始比较值大小，较小的值尾插到新链表上。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode trainningPlan(ListNode* l1, ListNode* l2) {
if(l1NULL)
return l2;
if(l2NULL)
return l1;

    ListNode* head=NULL;
    ListNode* tail=NULL;
    head=tail=(ListNode*)malloc(sizeof(ListNode));
    tail->next==NULL;
    while(l1&&l2)
    {
        if(l1->val<l2->val)
        {
            tail->next=l1;
            l1=l1->next;
            tail=tail->next;
         }
        else
        {
            tail->next=l2;
            l2=l2->next;
            tail=tail->next;
        }
    }
    if(l1)
    tail->next=l1;
    if(l2)
    tail->next=l2;

    ListNode* del=head;
    head=head->next;
    free(del);
    return head;
}

};

0 赞同 0 条回复

言之命至普通 2024年3月2日下午5:08

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
                if(l2==null){
            return l1;
        }
     ListNode merge = new ListNode(0);//定义一个辅助节点，这个节点只起辅助作用，这样temp不会是Null也不用判断是否是null
        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=l1;
}
if(l2!=null){
 temp.next=l2 ;
}
return merge.next;

    }
}

双指针问题，依次遍历两个数组，将较小的数值首先插入合并链表中，当一个链表为空时，将另一个链表的尾部全部插入合并链表中

时间复杂度：O(n+m)，n 和 m 表示两个链表长度
空间复杂度：O(1)

0 赞同 0 条回复

😴 普通 2024年3月2日下午4:56

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainningPlan(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 = l1 null ? l2:l1;
return merge.next;
}
}
算法思路：主要要设置一个辅助结点，依次比较两个链表中各结点值的大小，传给temp，最后要注意哪个链表已经为空。
时间复杂度O（n)
空间复杂度O（1）

0 赞同 0 条回复

CurDei 普通 2024年3月2日下午4:51

依次遍历两个数组，将较小的数值首先插入合并链表中，当一个链表为空时，将另一个链表的尾部全部插入合并链表中
空间O(N),时间O（1）
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainningPlan(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 条回复

lucky耶耶耶*👻*～普通 2024年3月2日下午4:49

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode l1, ListNode l2) {
        // write code here
        //新建一个辅助的头结点
        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 条回复

kfaebot 普通 2024年3月2日下午4:48

“`C++
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
//引入虚拟头节点
ListNode *vir=new ListNode(0);
ListNode *pt=vir;

    //当l1和l2均不为空链表时
    while(l1!=nullptr&&l2!=nullptr){
        if(l1->val<l2->val){
            pt->next=l1;
            l1=l1->next;
        }
        else{
            pt->next=l2;
            l2=l2->next;
        }
        pt=pt->next;
    }
    //当l1为空链表时
    if(l1==nullptr){
        pt->next=l2;
    }
    //当l2为空链表时
    else if(l2==nullptr){
        pt->next=l1;
    }
    return vir->next;
}

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

“`

0 赞同 0 条回复

Deckkker 普通 2024年3月2日下午4:37

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        if not l1 and not l2:
            return l1

        dummy = ListNode(-1)
        tmp = dummy


        while l1 and l2:
            if l1.val >= l2.val:
                tmp.next = l2
                l2 = l2.next
            else:
                tmp.next = l1
                l1 = l1.next
            tmp = tmp.next

        tmp.next = l1 if l1 else l2

        return dummy.next

设置一个dummy节点，标记新的链表。
tmp指针用来连接新的链表。
操作如下：
1、依次比较L1和L2元素的大小
2、小的元素则用tmp连接到新的链表
3、然后小元素链表的头指针（L1或L2）则移动到下个节点，继续比较。
4、重复上述操作直至其中一个链表全部连接到新的链表，然后接上另一个链表的剩余部分。
5、返回dummy.next。

时间复杂度O(m+n)：最差情况就是L1的长度m加上L2的长度n
空间复杂度O(1)：一个指针tmp一个伪节点dummy占常量空间。

0 赞同 0 条回复

mpweixin用户普通 2024年3月2日下午4:36

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

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


// 返回合并后的链表（注意返回的是虚拟头节点的下一个节点）

        return merge.next;
    }
}

0 赞同 0 条回复

NULL 普通 2024年3月2日下午2:57

class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 创建虚拟头节点
ListNode dummyHead = new ListNode();
ListNode prev = dummyHead;
ListNode curr1 = list1;
ListNode curr2 = list2;

    // 遍历两个链表并合并它们的元素
    while (curr1 != null && curr2 != null) {
        if (curr1.val < curr2.val) {
            prev.next = curr1;
            curr1 = curr1.next;
        } else {
            prev.next = curr2;
            curr2 = curr2.next;
        }
        prev = prev.next;
    }

    // 添加剩余的节点
    prev.next = (curr1 != null) ? curr1 : curr2;

    // 返回合并后的链表（注意返回的是虚拟头节点的下一个节点）
    return dummyHead.next;
}

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

0 赞同 0 条回复

　南木普通 2024年3月2日下午2:40

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

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

0 赞同 0 条回复

墨丘俐普通 2024年3月2日下午2:13

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while(l1!=null && l2!=null){
if(l1.val<l2.val){
cur.next = l1;
l1 = l1.next;
cur = cur.next;
}else{
cur.next = l2;
l2 = l2.next;
cur = cur.next;

        }


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

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

    }
    return dummy.next;

}

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

0 赞同 0 条回复

望普通 2024年3月2日下午1:18

”’python
class Solution:
def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
head = ListNode()
cur = head
if l1 None and l2 None:
return l1
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

    while l1:
        cur.next = l1
        cur = cur.next
        l1 = l1.next

    while l2:
        cur.next = l2
        cur = cur.next
        l2 = l2.next            
    return head.next

头节点，比较l1和l2，小的连接上，多余的单独遍历添加
时间:o(n + m)
空间:o(1)

0 赞同 0 条回复

普通 2024年3月2日下午1:14

class Solution {
public:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
if(l1nullptr) return l2;
if(l2nullptr) return l1;

    ListNode* head=new ListNode();
    ListNode* p=head;
    while(l1!=nullptr&&l2!=nullptr)
    {
        if(l1->val<=l2->val)  
        {
            p->next=l1;
            l1=l1->next;
        }
        else 
        {
            p->next=l2;
            l2=l2->next;
        }
        p=p->next;
    }
    if(l1==nullptr)   p->next=l2;
    if(l2==nullptr)   p->next=l1;
    return head->next;
}

};
打卡

0 赞同 0 条回复

Laboratory 普通 2024年3月2日下午12:27

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {

        // 新的头节点
        ListNode newHead = new ListNode(-1);
        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;
        }
        if(l1 == null) {
            cur.next = l2;
        }
        if(l2 == null) {
            cur.next = l1;
        }
        return newHead.next;
    }
}

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

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年3月2日下午12:11

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode(-1);
        ListNode temp = l3;

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

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

        return l3.next;
    }
}

时间复杂度o(n) 空间复杂度o(10

0 赞同 0 条回复

神经蛙普通 2024年3月2日下午12:08

struct ListNode* trainningPlan(struct ListNode* l1, struct ListNode* l2) {

struct ListNode merge;
struct 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;

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

0 赞同 0 条回复

ChenZhangHangTime 永久会员 2024年3月2日下午12:08

代码思路：
1.先设置好新数组和指向新数组的temp指针
2.写把旧数组的元素放进新数组的方法
3.将剩余的未放进新数组的元素放进新数组中
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode merge = new ListNode(0);
ListNode temp = merge;

    while(l1 != null && l2 != null){
        if(l1.val < l2.val){

            temp.next = l1;
            l1 = l1.next;
        } else {
            temp.next = l2;
            l2 = l2.next;
        }

        temp = temp.next;
    }

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

    return merge.next;
}

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

0 赞同 0 条回复

Bing0 普通 2024年3月2日上午11:15

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* trainningPlan(struct ListNode* l1, struct ListNode* l2) {
    if(l1 == NULL && l2 == NULL)
        return NULL;
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;
    struct ListNode* result = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* temp = result;
    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 result->next;
}

创建一个节点，遍历两个链表，val较小的那个连接到temp节点后
时间复杂度O(n);
空间复杂度O(1).

0 赞同 0 条回复

Yuki 永久会员 2024年3月2日上午10:51

class Solution {
public:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
ListNodedummyhead=new ListNode(0);
ListNodecur=dummyhead;
while(l1!=nullptr&&l2!=nullptr){
if(l1->valval){
cur->next=l1;
l1=l1->next;
}else{
cur->next=l2;
l2=l2->next;
}
cur=cur->next;
}
if(l1nullptr)cur->next=l2;
if(l2nullptr)cur->next=l1;
return dummyhead->next;

};

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

0 赞同 0 条回复

神经蛙普通 2024年3月2日上午10:22

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        // 自己定义辅助节点, 省的需要判断==null
        ListNode merge = new ListNode(0);
        ListNode temp = merge;
        // 比较公共部分
        while(l1 != null && l2 != null){
            // 小的接到temp后面
            if(l1.val < l2.val){
                temp.next = l1;
                l1 = l1.next;
            }else{
                temp.next = l2;
                l2 = l2.next;
            }
            // 移动temp
            temp = temp.next;
        }
        // 把剩下的直接接到后面
        temp.next = l1 == null ? l2 : l1;

        return merge.next;
    }
}

0 赞同 0 条回复

！。！普通 2024年3月2日上午10:08

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode trainningPlan(ListNode l1, ListNode* l2) {
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;
}
if(l1){
tmp->next = l1;
l1 = l1->next;
}
if(l2){
tmp->next = l2;
l2 = l2->next;
}
return merge->next;
}
};

时间o（m+n）
空间 o（1）

0 赞同 0 条回复

mpweixin用户普通 2024年3月2日上午9:45

“`java
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode dum = new ListNode(0), cur = dum;
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 ? l1 : l2; return dum.next; } } ```java 时间复杂度和空间复杂度都是O(M + N)

0 赞同 0 条回复

HU 普通 2024年3月2日上午9:33

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var trainningPlan = function(l1, l2) {
    // 设置返回值的前一个节点和当前节点
    let res = new ListNode(-1);
    let cur = res;

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

    cur.next = l1 != null ? l1 : l2;

    return res.next;
};

0 赞同 0 条回复

Free 普通 2024年3月2日上午8:26

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution 
{
public:
    ListNode* trainningPlan(ListNode* l1, ListNode* l2) 
    {
        ListNode* newhead = new ListNode();
        ListNode* tail = newhead;
        ListNode* cur1 = l1, *cur2 = l2;
        while(cur1 && cur2)
        {
            if(cur1->val < cur2->val)
            {
                tail->next = cur1;
                cur1 = cur1->next;
            }
            else
            {
                tail->next = cur2;
                cur2 = cur2->next;
            }
            tail = tail->next;
        }
        if(cur1)
            tail->next = cur1;
        if(cur2)
            tail->next = cur2;
        return newhead->next;
    }
};

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

0 赞同 0 条回复

Yox 普通 2024年3月2日上午4:41

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

class Solution:
def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[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

时间o（m+n）
空间 o（1）

0 赞同 0 条回复

在线coding 普通 2024年3月2日上午12:01

public class ListNode {
- int val;
- ListNode next;
- ListNode() {}
- ListNode(int val) { this.val = val; }
- ListNode(int val, ListNode next) { this.val = val; this.next = next; }
- }
  */
  class Solution {
  //总共比较2n次，时间复杂度为O(n),空间复杂度固定为O(1)
  public ListNode trainningPlan(ListNode l1, ListNode l2) {
  //选择dumyNode作为返回链表
  ListNode dumyNode = new ListNode(-1);
  //双指针解法（同时遍历两条链表）
  ListNode temp = dumyNode;
  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;
  // l1 null ? temp.next = l2 : temp.next = l1;
  return dumyNode.next;
  }
  }

0 赞同 0 条回复

Let it be 永久会员 2024年3月1日下午11:22

class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);ListNode now = head;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
now.next = l1;
l1 = l1.next;
}else{
now.next = l2;
l2 = l2.next;
}
now = now.next;
}
now.next = l1 != null ? l1 : l2;
return head.next;
}
} 时间复杂O（l1+l2）空间复杂O（1）

0 赞同 0 条回复

统一绿茶Gin 普通 2024年3月1日下午11:15

合并两个排序的链表java

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode trainningPlan(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 条回复

还不多喝热水普通 2024年3月1日下午10:44

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode current = dummyHead;
        ListNode current1 = l1;
        ListNode current2 = l2;
        while(current1 != null && current2 != null) {
            // 将当前节点的next指针指向值较小的节点，并将值较小的链表后移一位
            if(current1.val <= current2.val) {
                current.next = current1;
                current1 = current1.next;
            }
            else {
                current.next = current2;
                current2 = current2.next;
            }
            // 当前节点后移一位
            current = current.next;
        }
        // 将剩余的节点挂在当前节点后
        if (current1 == null) {
            current.next = current2;
        }
        if (current2 == null) {
            current.next = current1;
        }
        // 返回虚拟节点的next节点
        return dummyHead.next;
    }
}

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

0 赞同 0 条回复

while(1) 普通 2024年3月1日下午10:35

“`C++
class Solution {
public:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
ListNode *dum = new ListNode(0);
ListNode *cur = dum;
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? l1 : l2;
return dum->next;
}
};
“`
方法：双指针
时间复杂度：o(n)
空间复杂度：o(1)
如有问题，欢迎指正！

0 赞同 0 条回复

紫芝普通 2024年3月1日下午10:31

时间复杂度：O(n)
空间复杂度：O(1)
思路：创建一个虚拟头节点prehead, 依次将两个有序链表的值按照顺序添加到prehead后边，然后返回prehead->next即可。

“`C++
class Solution {
public:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
if (l1 != nullptr && l2 != nullptr) {
ListNode *prehead = new ListNode(0);
ListNode *cur = prehead;
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 (l2) {
l1 = l2;
}
while (l1) {
cur->next = l1;
cur = cur->next;
l1 = l1->next;
}
l1 = prehead->next;
delete prehead;
return l1;
} else if (l1 != nullptr) {
return l1;
} else{
return l2;
}

};

“`

0 赞同 0 条回复

Raphtalia. 普通 2024年3月1日下午10:29

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode trainningPlan(ListNode* l1, ListNode* l2) {
ListNode* merge = new ListNode(0);
ListNode* tmp = merge;
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 merge->next;
}
};
时空复杂度均为O（n+m）

0 赞同 0 条回复

机电皮怪永久会员 2024年3月1日下午10:10

时间复杂度o（n）
空间复杂度o（1）
cpp
“””
class Solution {
public:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
if ( l1 nullptr && l2 nullptr )
{
return nullptr;
}
if ( l1 nullptr )
{
return l2;
}
if ( l2 nullptr )
{
return l1;
}
ListNode* dummyhead = new ListNode(999);
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;
}

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

    return dummyhead->next;
}

};
“””

0 赞同 0 条回复

30tcq 普通 2024年3月1日下午10:01

思路：直接判断两个链表是否非空，然后将新链表的指针分别指向l1、l2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
        ListNode *merge = new ListNode(0);
        ListNode *rs = merge;
        while(l1 && l2){      //两个链表都非空时，根据元素的值决定
            if(l1->val <= l2->val){
                rs->next = l1;
                l1 = l1->next;
            }else{
                rs->next = l2;
                l2 = l2->next;
            }
            rs = rs->next;
        }
        rs->next = l1 ? l1 : l2;
        return merge->next;
    }
};

犯错
忘记加头结点，返回结果时忘记不加头结点
时间复杂度
O(n)
空间复杂度
O(n)

0 赞同 0 条回复

王位詮釋普通 2024年3月1日下午9:54

class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode head = new ListNode();
ListNode temp = head;
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(l1null){
temp.next = l2;
}else{
temp.next = l1;
}
return head.next;
}
}
时间复杂度：O(l1+l2)，遍历了两条链表，空间复杂度为O(1)
思路：遍历两条链表的同时进行比较，将小的节点往新的链表中插入，最终获得一个排序后的链表。如果遍历过程中有一条链表遍历完了，那就直接将另一条链表的后续元素插入排序后的链表。

0 赞同 0 条回复

叫不醒装睡的人普通 2024年3月1日下午9:46

class Solution {
    // 利用递归合并两个有序链表
    // 考虑链表为空的情况
    // 把每次合并看作是小链表汇聚成大链表
    // 两个链表节点中的数值比较大小，数值小的节点后继指向下一个有序小链表
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        if (l1 == null && l2 == null) {
            return null;
        }
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        if (l1.val < l2.val) {
            l1.next = trainningPlan(l1.next, l2);
            return l1;
        } else {
            l2.next = trainningPlan(l1, l2.next);
            return l2;
        }
    }
    // 时间复杂度为 O(m + n) 
    // 两个链表如果等长，则需要比较所有的元素
    // 假定一个链表长 m，另一个链表长 n， m > n，为啥时间复杂度是 O(m + n) 而不是 O(n)
    // 空间复杂度为 O(m + n) 
    // 每一次递归都要记录当时的小链表的信息，存在相当的空间开销
}

0 赞同 0 条回复

Jimmy 普通 2024年3月1日下午9:23

新建一个链表，依次比较两个排序链表的值，值小的先加入新建链表，用到了虚拟节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
        ListNode *dummyHead = new ListNode(0);//新建链表用于填充最终结果，此节点为虚拟节点
        ListNode *temp = dummyHead;
        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 == nullptr) ? l2 : l1;
        return dummyHead->next;
    }
};

0 赞同 0 条回复

云无深雁影普通 2024年3月1日下午9:19

class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode head = new ListNode();
ListNode ptr = head;
while(l1 != null & l2 != null){
if(l1.val > l2.val){
ptr.next = l2;
l2 = l2.next;
}
else{
ptr.next = l1;
l1 = l1.next;
}
ptr = ptr.next;
}
if(l1null)
ptr.next = l2;
else
ptr.next = l1;
return head.next;

}
双指针
空间复杂度O1
时间复杂度O(n+m)

0 赞同 0 条回复

进取普通 2024年3月1日下午9:18

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode trainningPlan(ListNode* l1, ListNode* l2) {
ListNode* dummyhead = new ListNode(0);
ListNode* cur = dummyhead;
while (l1 != nullptr && l2 != nullptr){
if(l1->val >= l2->val){
cur->next = l2;
l2 = l2->next;
}
else{
cur->next = l1;
l1 = l1->next;
}
cur = cur->next;
}
//if(l1 nullptr) cur->next = l2;
//else cur->next = l1;
cur->next = l1 nullptr?l2:l1;
return dummyhead->next;
}

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

0 赞同 0 条回复

heathhou 普通 2024年3月1日下午9:08

class Solution {
public:
    ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
        ListNode * l = new ListNode();
        ListNode * head = l;
        while(l1 != nullptr && l2 != nullptr){
            if(l1->val <= l2->val){
                l->next = l1;
                l = l->next;
                l1 = l1->next;
            }
            else{
                l->next = l2;
                l = l->next;
                l2 = l2->next;
            }
        }
        // l1 与 l2 至少有一个为空
        if(l1 == nullptr){
            l->next = l2;
        }
        else {
            l->next = l1;
        }

        return head->next;
    }
};

思路：建立一个头结点，表示新创建的链表的头结点。然后将l1与l2依次比大小，将小的插入到新链表后面，直到l1与l2至少其中一个被遍历完。然后将剩下的直接插到新链表的后面。
时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

Monou 普通 2024年3月1日下午9:07

时间复杂度O(
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {

    ListNode head = new ListNode(0);

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

}

0 赞同 0 条回复

是hua不是pua 普通 2024年3月1日下午8:58

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

双指针

0 赞同 0 条回复

MARS 普通 2024年3月1日下午8:55

day1

function trainningPlan(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    //设置一个节点来连接两条链表
    let node: ListNode | null = new ListNode()
    let cur: ListNode | null = node
    //遍历两条链表，其中一条遍历完就结束
    while (l1 && l2) {
        if (l1.val <= l2.val) {
            let newNode: ListNode | null = l1  //保存下l1当前节点
            l1 = l1.next  //让l1继续向下走
            newNode.next = null //断开l1当前节点下面的链表
            cur.next = newNode //连上节点
            cur = cur.next //继续向下走
        } else {
            let newNode: ListNode | null = l2  //保存下l2当前节点
            l2 = l2.next  //让l2继续向下走
            newNode.next = null //断开l2当前节点下面的链表
            cur.next = newNode
            cur = cur.next
        }
    }
    if (l1) { //看那条链条还有节点
        cur.next = l1
    } else {
        cur.next = l2
    }
    return node.next
};

0 赞同 0 条回复

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

共以下 80 个回答

Definition for singly-linked list.

class ListNode(object):

def init(self, val=0, next=None):

self.val = val

self.next = next

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

# 回答此问题取消回复

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

共以下 80 个回答

Definition for singly-linked list.

class ListNode(object):

def init(self, val=0, next=None):

self.val = val

self.next = next

Definition for singly-linked list.

class ListNode:

def init(self, val=0, next=None):

self.val = val

self.next = next

# 回答此问题 取消回复

# 回答此问题取消回复