為愛而生普通 2024年12月20日下午1:42

“`java
//解题思路：伪头节点+新链表
class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode f = new ListNode(0);
ListNode cur = f;
while(l1 != null && l2 != null){
if(l1. val < l2. val){ ListNode p = new ListNode(l1.val); cur.next = p; cur = cur.next; l1 = l1.next; } else if(l1.val > l2.val){
ListNode p = new ListNode(l2.val);
cur.next = p;
cur = cur.next;
l2 = l2.next;
}
else{
ListNode p1 = new ListNode(l1.val);
ListNode p2 = new ListNode(l2.val);
cur.next = p1;
cur = cur.next;
cur.next = p2;
cur = cur.next;
l1 = l1.next;
l2 = l2.next;
}
}
if(l1 == null && l2 != null){
cur.next = l2;
}
else if(l2 == null && l1 != null){
cur.next = l1;
}
else{
cur.next = null;
}
return f.next;
}
}

0 赞同 0 条回复

宇晴普通 2024年12月2日下午10:54

用迭代法

var trainningPlan = function(l1, l2) {
    const prehead = new ListNode(-1);
    let 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;
};

0 赞同 0 条回复

YULONG 永久会员 2024年11月30日上午1:49

/**
解题思路：
两链表皆为有序链表，每次取两链表较小的作为新节点
复杂度分析：
需遍历完两个链表，时间复杂度O(N)
 */
class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {

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

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

        ListNode dummy = new ListNode(-1);
        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;
        }

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

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

        return dummy.next;



    }
}

0 赞同 0 条回复

泽阳普通 2024年11月29日上午10:10

拷贝原链表，不影响原链表的数据

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        ListNode sentinel = new ListNode();
        ListNode cur = sentinel;
        while (l1 != null || l2 != null) {
            if (l1 != null && (l2 == null || l1.val <= l2.val)) {
                cur.next = new ListNode(l1.val);
                l1 = l1.next;
            } else {
                cur.next = new ListNode(l2.val);
                l2 = l2.next;
            }
            cur = cur.next;
        }

        return sentinel.next;
    }
}

0 赞同 0 条回复

月下足迹普通 2024年11月29日上午10:04

class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
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;

    }

    //如果其中一个链表遍历完了，剩下那个链表直接连上链表尾部
    if(l1!=null) {
        current.next = l1;
    }
    if(l2!=null) {
        current.next = l2;
    }

    return dummy.next;
}

}

0 赞同 0 条回复

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

创建头节点，每一次比较两个链表的值

# 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]:
        dummy = ListNode(0)
        res = dummy
        while l1 and l2:
            if l1.val < l2.val:
                res.next = l1
                l1 = l1.next
            else:
                res.next = l2
                l2 = l2.next
            res = res.next
        if l1:
            res.next = l1
        else:
            res.next = l2
        return dummy.next

0 赞同 0 条回复

桃桃摇摇奶昔° 普通 2024年11月27日上午11:04

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;

    }
}

事件复杂度O（N）
空间复杂度O（1）

0 赞同 0 条回复

Lil Lee_ 普通 2024年11月26日下午10:23

//双指针，有序链表合并
/**
 * 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) {
        //初始化链表l3
        ListNode l3 = new ListNode(0);
        //虚拟头指针
        ListNode cur = l3;
        //循环遍历，将l1和l2中较小的放前面
        while(l1 != null && l2 != null){
            if(l1.val <= l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next; 
            }
            cur = cur.next;
        }
    //判断l1和l2都空时才结束    
    cur.next = l1 != null ? l1 : l2;
    return l3.next;
    }
}

//空间复杂度为N+M，递归
/**
 * 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;
        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年11月25日下午6:31

“`python
class Solution(object):
def trainningPlan(self, l1, l2):
//初始化一个辅助节点
dummy=ListNode(0)
cur=dummy
//两个链表都非空进行操作，将更小的值加入新链表，并逐步遍历
while l1 and l2:
if l1.val

0 赞同 0 条回复

yelinliner 普通 2024年11月24日下午5:33

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        // 辅助节点：最后返回的是merge.next，所以不影响结果，只是为了避免nullpoint
        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;
        }
        // 合并后 l1 和 l2 最多只有一个还未被合并完
        // 直接将链表末尾指向未合并完的链表即可
        temp.next = l1 == null ? l2 : l1;
        return merge.next;
    }
}

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

0 赞同 0 条回复

LovLe 普通 2024年11月23日下午10:04

# 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 None #这三种情况，都可以归到最后的拼接中
        # if not l1: return l2
        # if not l2: return l1
        p1,p2=l1,l2
        # pre= p1 if p1.val<=p2.val else p2
        dummyhead=ListNode(-1)  #虚拟头节点，不用关注头节点谁先开始
        pre=dummyhead
        # if pre==p1:
        #     p1=p1.next
        # else:
        #     p2=p2.next
        while p1 and p2:    #双方都有节点可比较
            if p1.val<=p2.val:  #更新
                pre.next=p1
                p1=p1.next
            else:
                pre.next=p2
                p2=p2.next
            pre=pre.next    # 无论哪一个，都要更新pre，向前移动！！
        # while p1:
        #     pre.next=p1
        # while p2:
        #     pre.next=p2
        pre.next=p1 if p1 else p2   #把剩下的放过来，只用一个next拼接，剩下的已经有序

        return dummyhead.next      #使用虚拟头节点，模板，返回值

递归法：

只看着当前的两个节点比较
- 根据大小，参数中移动l1/l2的指针
终止条件：
- 某一方为空，返回另一个节点

# 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 None
        if not l1: return l2
        if not l2: return l1
        if l1 and l2:
            if l1.val<=l2.val:
                l1.next=self.trainningPlan(l1.next,l2)  # 返回的只是一个当前节点cur
                return l1   #返回当前节点
            else:
                l2.next=self.trainningPlan(l1,l2.next)
                return l2

时间复杂度：O(n+m) 合并两个链表，需要遍历这两个链表长度
空间复杂度：O(1) 用了额外的1个虚拟头节点

0 赞同 0 条回复

ㅤ牛马学编程普通 2024年11月23日下午6:06

“`java
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; } } } 时间复杂度:O(n1 + n2) 空间复杂度:O(1)

0 赞同 0 条回复

无言永久会员 2024年11月23日下午4:54

/**
 * 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();
        ListNode* cur = dummy;
        while(l1 != nullptr && l2 != nullptr) {
            ListNode* node = new ListNode();
            if(l1->val >= l2->val) {
                node->val = l2->val;
                l2 = l2->next;
            } else if(l1->val < l2->val) {
                node->val = l1->val;
                l1 = l1->next;
            }
            cur->next = node;
            cur = cur->next;
        }
        if(l1 != nullptr) {
            cur->next = l1;
        }
        if(l2 != nullptr) {
            cur->next = l2;
        }
        return dummy->next;
    }
};
时间复杂度: O(m+n) m 和 n 分别是链表 l1 和 l2 的长度
空间复杂度: O(1)

0 赞同 0 条回复

借来的猫普通 2024年11月23日上午10:39

class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode dumhead= new ListNode(1);
ListNode zhizhen=dumhead;
while(l1!=null&&l2!=null) {
if(l1.val<l2.val){
zhizhen.next=l1;
l1=l1.next;
}
else{
zhizhen.next=l2;
l2=l2.next;
}
zhizhen=zhizhen.next;
}
if(l1null){
zhizhen.next=l2;}
else {zhizhen.next=l1;}
return dumhead.next;
}
}
时间复杂度: O(n1 + n2)，其中 n1 是 list1 的长度，n2 是 list2 的长度。
空间复杂度: O(1)，因为使用了常数额外空间。

0 赞同 0 条回复

捕风永久会员 2024年11月22日下午10:25

时间复杂度: O(n1 + n2)，其中 n1 是 list1 的长度，n2 是 list2 的长度。
空间复杂度: 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 mergeTwoLists(ListNode list1, ListNode list2) {
        // 创建合并链表merge
        ListNode merge = new ListNode(0); // 头节点的值为 0 只是为了占位，帮助简化链表合并的操作（虚拟头节点merge）
        ListNode temp = merge;  // temp 是一个 指向 merge 的指针，作用是保持对 merge 节点的引用

        // 循环遍历
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                // 如果不设置0节点，temp可能为空指针，.next的值会出现异常
                // 此时如果添加判断语句，代码会变得复杂
                temp.next = list1;  
                list1 = list1.next;
            }else{
                temp.next = list2;
                list2 = list2.next;
            }

            temp = temp.next;
            // 当其中一个指针指向空，即其中一个链表遍历完时，跳出循环

        }

        // 用三元运算符判断到底是哪一个链表遍历完了
        temp.next = list1 == null ? list2:list1;

        // temp 保证不丢失 merge
        // 最终，返回合并后的链表的头节点merge.next，因为 merge 本身是一个哑节点，没有包含实际的数据
        return merge.next;


    }
}

0 赞同 0 条回复

岱永久会员 2024年11月22日下午4:59

代码

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

}

0 赞同 0 条回复

土豆哥普通 2024年11月21日下午11:58

“`java
25.合并两个的链表
class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {

        ListNode dummy = new ListNode();
        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!=null)  cur.next = l1;
        else   cur.next = l2;

        return dummy.next;
    }
}

0 赞同 0 条回复

biangbb 普通 2024年11月21日下午10:38

class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode first=l1,second=l2,head=new ListNode(),h=head;
while(first!=null&&second!=null){
if(first.val<=second.val){
head.next=first;
first=first.next;
}else{
head.next=second;
second=second.next;
}
head=head.next;
}
while(first!=null){
head.next=first;
first=first.next;
head=head.next;
}
while(second!=null){
head.next=second;
second=second.next;
head=head.next;
}
return h.next;
}
}
简化：
1. 后续不需要循环，因为是一个链

0 赞同 0 条回复

爱姆露普通 2024年11月21日下午10:26

// 创建一个虚拟头节点，简化链表操作
ListNode* dummy = new ListNode(0);
ListNode* temp = dummy;

    // 遍历两个链表，直到其中一个为空
    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) ? l1 : l2;

    // 返回新链表的头节点，即虚拟头节点的下一个节点
    return dummy->next;

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

0 赞同 0 条回复

Poetry and distance 永久会员 2024年11月21日下午9:14

思路：相同长度部分进行同步遍历比较，选出最小的，如果其中有一个为空了，则直接连接另一个链表，因为是有序的
代码：
/**
 * 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 merge=new ListNode(0);
        ListNode temp=merge;
        while(list1!=null&&list2!=null){
            if(list1.va<list2.val){
                temp.next=list1;
                list1=list1.next;
            }
            else{
                temp.next=list2;
                list2=list2.next;
            }
            temp=temp.next;
        }
        temp.next=list1!=null?list1:list2;
        return merge.next;
    }
}
时间复杂度：O(m+n),m,n为二个链表长度
空间复杂度:O(1)

0 赞同 0 条回复

橙子陈爱吃橙子普通 2024年11月21日下午7:46

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

        return merge.next;

    }
}

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

0 赞同 0 条回复

mpweixin用户普通 2024年11月21日下午2:08

解题思路
本题可以采用双指针迭代的思路来解决。首先创建一个虚拟头节点（哨兵节点），这样可以统一处理链表头部的逻辑。然后使用两个指针分别遍历两个链表，比较当前两个指针指向的节点值的大小，将较小的节点接入新链表中，并将对应的指针向后移动。这个过程就像是对两串项链进行归并，每次都选择数值较小的珠子串接到新链表上。
当其中一个链表遍历完成后，我们只需要将另一个链表的剩余部分直接接到新链表的末尾即可。这是因为输入的两个链表本身就是有序的，所以未遍历完的部分一定大于已经合并的所有节点，并且它们本身保持着有序性。

复杂度分析
时间复杂度：O(n + m)，其中n和m分别是两个链表的长度。我们需要遍历两个链表各一次。
空间复杂度：O(1)，只使用了常数个指针变量，没有使用额外的空间。

代码实现

“`c++
class Solution {
public:
ListNode* trainningPlan(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 == nullptr ? l2 : l1;

    // 返回合并后的链表（跳过哨兵节点）
    return merge->next;
}

};

0 赞同 0 条回复

zing 普通 2024年11月21日下午1:30

为什么在判断链表是否为空时是判断 while index1，而不是while index.next

class Solution:
    def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        index1, index2 = l1, l2
        ans = ListNode(0, None)
        bummy = ans

        while index1 and index2:
            if index1.val > index2.val:
                bummy.next = index2

                index2 = index2.next
            else:
                bummy.next = index1

                index1 = index1.next
            bummy = bummy.next

        if index1:
            bummy.next = index1
        elif index2:
            bummy.next = index2

        return ans.next

0 赞同 0 条回复

Renasc 普通 2024年11月21日上午11:45

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

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        // 建立虚拟头结点
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;

        // 合并左右链表
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }

        // 将剩下的链表接上
        curr.next = (l1 != null) ? l1 :l2;

        // 返回头结点
        return dummy.next;
    }

}

0 赞同 0 条回复

Tom Yuan 普通 2024年11月21日上午10:56

双指针先建立一个新的LL 拿到头然后位于两个链表上的指针比较值大小小的就往新的list上塞
随后如果一个走完了另一个还没走完说明另一个剩下的都比走完的所有值大然后将其拼接到结果上

因为一开始创建了一个特殊值的头节点0 取结果时记得把他扣掉

def trainningPlan(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        new_start = ListNode(0)
        cur = new_start

        while l1 != None and l2 != None:
            if l1.val > l2.val:
                cur.next = l2
                l2 = l2.next
            else:
                cur.next = l1
                l1 = l1.next
            cur = cur.next

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

        return new_start.next

time: O(m+n)
space: O(1) 头节点剩余的都是建立的next

0 赞同 0 条回复

C。普通 2024年11月21日上午10:48

思路

ListNode merge = new ListNode(0);
ListNode temp = merge;//防止空指针异常
创建临时节点，比较L1,L2的值，temp.next指向较小的值，直到链表遍历结束

代码

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

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

0 赞同 0 条回复

Rad 普通 2024年11月21日上午10:37

/**
* 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 head;
if(l1.val <= l2.val){
head = l1;
l1 = l1.next;
}
else {
head = l2;
l2 = l2.next;
}
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;
}
node.next = l1 null? l2:l1;
return head;
}
}
时间复杂度O（m+n）
空间复杂度O（1）

0 赞同 0 条回复

jaron 普通 2024年11月21日上午10:13

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

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        // 确定头结点
        ListNode head;
        if (l1.val <= l2.val) {
            head = l1;
            l1 = l1.next;
        } else {
            head = l2;
            l2 = l2.next;
        }
        ListNode cur = head;
        // 选择较小的接上
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        // 若果一个搞完了，直接把另一个剩下的全部接上
        cur.next = l1 == null ? l2 : l1;
        return head;
    }
}

0 赞同 0 条回复

mpweixin用户普通 2024年11月21日上午9:37

打卡
”’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* dum = new ListNode(-1);
ListNode* res = dum;
while(l1 && l2){
if(l1->valval){
res->next = l1;
l1 = l1->next;
}else{
res->next = l2;
l2 = l2->next;
}
res = res->next;
}
if(l1){
res->next = l1;
}
if(l2){
res->next = l2;
}
return dum->next;

};

”’

0 赞同 0 条回复

Pendulumpal 普通 2024年11月21日上午12:16

用双指针遍历这两个链表

“`c++
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
ListNode* p1=l1;
ListNode* p2=l2;
ListNode* head=new ListNode(-1,nullptr);
ListNode* ans=head;
while((l1!=nullptr)||(l2!=nullptr)){
if(l1==nullptr){head->next=new ListNode(l2->val);l2=l2->next;head=head->next;continue;}
if(l2==nullptr){head->next=new ListNode(l1->val);l1=l1->next;head=head->next;continue;}
if((l1->val)>(l2->val)){
head->next=new ListNode(l2->val);
l2=l2->next;
}else{
head->next=new ListNode(l1->val);
l1=l1->next;
}
head=head->next;
}
return ans->next;
}
“`

0 赞同 0 条回复

Firefly 普通 2024年11月20日下午11:56

class Solution {
public:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
ListNode* pHead = nullptr;
ListNode* pCur = nullptr;
while (l1 != nullptr && l2 != nullptr) {
ListNode* pTmp = nullptr;
if (l1->val > l2->val) {
pTmp = l2;
l2 = l2->next;
} else {
pTmp = l1;
l1 = l1->next;
}

        if (pHead == nullptr) {
            pHead = pTmp;
            pCur = pTmp;
        } else {
            pCur->next = pTmp;
            pCur = pCur->next;
        }
    }

    if (l1 != nullptr) 
    {
        if (pHead == nullptr) 
         pHead = l1;
        else 
         pCur->next = l1;
    } 
    else if (l2 != nullptr) 
    {
         if (pHead == nullptr) 
         pHead = l2;
        else 
         pCur->next = l2;
    }
    return pHead;
}

};
时间复杂度O（n）

0 赞同 0 条回复

咕普通 2024年11月20日下午11:47

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) 空间O(1)

0 赞同 0 条回复

陆狗陆狗普通 2024年11月20日下午11:25

题解

class Solution {
    public ListNode trainningPlan(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        // 新链表的虚拟头结点
        ListNode merge=new ListNode();
        // 新链表的遍历节点
        ListNode mergeP=merge;
        ListNode node1=l1;
        ListNode node2=l2;
        // 【错误点1】
        while(node1!=null && node2!=null){
            if(node1.val<=node2.val){
                // node1比node2小于等于，node1加入新的链表中
                mergeP.next=node1;
                mergeP=node1;
                // node1往后
                node1=node1.next;
                if(node1==null){
                    // l1已经没有元素了，把l2剩余的全部加入新的链表
                    mergeP.next=node2;
                }
            }else{
                mergeP.next=node2;
                mergeP=node2;
                node2=node2.next;
                if(node2==null){
                    mergeP.next=node1;
                }
            }
        }
        return merge.next;
    }
}

错误点1 ：&&条件写成了 || ，while里面的条件是满足了才执行循环

0 赞同 0 条回复

🌟 普通 2024年11月20日下午11:15

时间On
class Solution {
public:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
if (l1 nullptr)
return l2;
if (l2 nullptr)
return l1;
ListNode* l3;
if(l1->valval){
l3=l1;
l1=l1->next;
}else{
l3=l2;
l2=l2->next;
}
ListNode* cur = l3;
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 = l2;
    } else if (l2 == nullptr) {
        cur->next = l1;
    } else {
        cur->next = nullptr;
    }
    return l3;
}

};

0 赞同 0 条回复

遇事不决睡大觉普通 2024年11月20日下午11:10

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

}

0 赞同 0 条回复

Kisara 普通 2024年11月20日下午11:02

““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 p1=l1;
ListNode p2=l2;
ListNode l3=new ListNode(0);
ListNode p3=l3;

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

   if(p1==null)
      p3.next=p2;
      else p3.next=p1;
    return l3.next;
}

}
时间O（n）空间O（1）

0 赞同 0 条回复

越努力越幸运普通 2024年11月20日下午11:02

“`c++
class Solution {
public:
ListNode* trainningPlan(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;
}

};

“`
//跟着地哥现学
//为什么我上传的markdown格式不对啊？本地是可以正常显示的

0 赞同 0 条回复

晓宇普通 2024年11月20日下午10:53

/**
* 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 p = l1, *q = l2,h;
ListNode new_head;
new_head.next = h;
while(p || q){
if(p && (p->val < q->val || !q)){
ListNode *node = new ListNode(p->val);
h->next = node;
h = h->next;
p = p->next;
}
if(q && (q->val < p->val || !p)){
ListNode *node = new ListNode(q->val);
h->next = node;
h = h->next;
q=q->next;
}
}
return new_head.next->next;
}
};
时间复杂度o(m+n)，空间复杂度o(1)

0 赞同 0 条回复

lQl 永久会员 2024年11月20日下午10:51

双指针

class Solution {
    public ListNode trainningPlan(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;
            }else{
                cur.next=l2;
                l2=l2.next;
            }
            cur=cur.next;
        }
        if(l1==null){
            cur.next=l2;
        }else{
            cur.next=l1;
        }
        return dum.next;
    }
}

0 赞同 0 条回复

时光烙印普通 2024年11月20日下午10:45

递归：

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 l1 is None:
return l2
elif l2 is None:
return l1
elif l1.val < l2.val:
l1.next = self.trainningPlan(l1.next, l2)
return l1
else:
l2.next = self.trainningPlan(l1, l2.next)
return l2

0 赞同 0 条回复

张君雅小妹妹普通 2024年11月20日下午10:38

定义一个前序节点

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

        return head.next;

    }

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

0 赞同 0 条回复

生活在经验里普通 2024年11月20日下午10:01

//go题解
func trainningPlan(l1 *ListNode, l2 *ListNode) *ListNode {
if l1 nil {
return l2
}
if l2 nil {
return l1
}

var newList *ListNode
if l1.Val < l2.Val {
    newList = l1
    l1 = l1.Next
} else {
    newList = l2
    l2 = l2.Next
}

tmp := newList
for l1 != nil && l2 != nil {
    if l1.Val < l2.Val {
        tmp.Next = l1
        l1 = l1.Next
    } else {
        tmp.Next = l2
        l2 = l2.Next
    }
    tmp = tmp.Next
}

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

}

0 赞同 0 条回复

mpweixin用户普通 2024年11月20日下午9:42

class Solution {
public:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {

    ListNode* result = new ListNode(0);
    ListNode* p = result;
    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;
    }
    else{
        p->next = l2;
    }
    return result->next;
}

};
思路：设一个头结点，每次比较l1与l2当前指针所指的值，将小的节点接到头结点中，同时指针移动；最后会有一个链表没有全部比较完，因为题目写的有序，所以直接接在结果链表的后面即可，返回值取头结点的下一位。
时间复杂度O(n+m)，空间复杂度O(1)

0 赞同 0 条回复

mpweixin用户普通 2024年11月20日下午9:37

a.思路分析
1.定义一个虚拟节点，用于改善程序逻辑。
2.当l1和l2指针均不为nullptr时，将较小的节点赋给虚拟节点下一个，并且指针向下移动一位。
3.判断l1和l2不空的那个，将其赋值给虚拟节点
4.返回虚拟节点的下一个，保证输入输出的有效性。
b.代码

class Solution {
public:
    ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
        ListNode* cur1 = l1;
        ListNode* cur2 = l2;
        ListNode* newHead = new ListNode();
        ListNode* curList = newHead;

        while(cur1!=nullptr && cur2!=nullptr)
        {

            if(cur1->val < cur2->val) 
            {
                curList->next = cur1;
                cur1 = cur1->next;
            }
            else 
            {
                curList->next = cur2;
                cur2 = cur2->next;
            }

            curList = curList->next;

        }
        //这里需要注意循环不变量
        if(cur1!=nullptr) curList->next = cur1;
        else if(cur2!=nullptr) curList->next = cur2;

        return newHead->next;
    }
};
c.时间复杂度：o(n)，n为l1和l2链表长度的总和；空间复杂度o(1)，额外使用了常数级的内存空间。

0 赞同 0 条回复

. 普通 2024年11月20日下午9:31

时间o(n),空间o(1)
后面写麻烦了，直接等于剩余的l1或l2所指的指针就可以了
/**
* 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 merged = new ListNode();
ListNode head = merged;
if(l1 null && l2 null){
return null;
}
while(l1 != null && l2 != null){
if(l1.val < l2.val){
merged.next = l1;
merged = merged.next;
l1 = l1.next;
}
else{
merged.next = l2;
merged = merged.next;
l2 = l2.next;
}
}
while(l1 != null){
merged.next = l1;
merged = merged.next;
l1 = l1.next;
}
while(l2 != null){
merged.next = l2;
merged = merged.next;
l2 = l2.next;
}
return head.next;
}
}

0 赞同 0 条回复

momo 普通 2024年11月20日下午9:17

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]:
dummy = ListNode(1)
cur = dummy
while(l1 or l2):
if l1 and l2:
if l1.val <= l2.val:
cur.next = ListNode(l1.val)
l1 = l1.next
else:
cur.next = ListNode(l2.val)
l2 = l2.next
cur = cur.next
else:
if l1:
cur.next = l1
l1 = None
else:
cur.next = l2
l2 = None
return dummy.next
时间复杂度O(max(m,n))
空间复杂度O(1)

0 赞同 0 条回复

Jerry 普通 2024年11月20日下午9:04

class Solution {
public:
    ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
        ListNode* myhead = new ListNode(-1);
        ListNode* cur = myhead;
        while(l1 && l2){
            if(l1->val < l2->val){
                cur->next = l1;
                l1 = l1->next;
            }
            else{
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if(l1){
            cur->next = l1;
        }
        if(l2){
            cur->next = l2;
        }
        return myhead->next;
    }
};

时间o(n)
空间o(1)

0 赞同 0 条回复

Carry on 普通 2024年11月20日下午8:57

class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
// 定义一个虚拟头节点
ListNode dummy = new ListNode(-1);
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;
    }

    // 如果一个链表还有剩余节点，直接接到结果链表后面
    if (l1 != null) {
        current.next = l1;
    }
    if (l2 != null) {
        current.next = l2;
    }

    // 返回合并后的链表
    return dummy.next;
}

}

0 赞同 0 条回复

parsons 普通 2024年11月20日下午8:55

class Solution {
public:
ListNode* trainningPlan(ListNode* l1, ListNode* l2) {
//1.判断空的情况
if(l1 nullptr)
return l2;
if(l2 nullptr)
return l1;
//2.创建保存节点、头节点
ListNode *resHead = new ListNode(-1);
ListNode *pre = resHead;
//3.开始比较
while(l1 != nullptr && l2 != nullptr){
//4.比较l1 l2的大小，并且加到pre后面
if(l1->val > l2->val){
pre->next = l2;
l2 = l2->next;
}else{
pre->next = l1;
l1 = l1->next;
}
//5.pre向后移动
pre = pre->next;
}

    //6.长度不一致的时候，把长的链表剩余部分直接加到排序完的链表后面
    if(l1 != nullptr){
        pre->next = l1;
    }else{
        pre->next = l2;
    }
    //7.返回保存节点后一个节点
    return resHead->next;
}

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

0 赞同 0 条回复

hjx 普通 2024年11月20日下午8:52

class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode dummy=new ListNode(-1) ;
ListNode p1=l1,p2=l2,p=dummy;
while(p1!=null && p2!=null){
if(p1.val<=p2.val){
p.next=p1;
p1=p1.next;
p=p.next;
}else{
p.next=p2;
p2=p2.next;
p=p.next;
}
}
p.next=(p1!=null?p1:p2);
return dummy.next;
}
}
时间O（n）,空间o(1)

0 赞同 0 条回复

Xiang. 永久会员 2024年11月20日下午8:50

/**
* 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(l1null||l2null) return l1null?l2:l1;
else if(l1.val<l2.val){
l1.next=trainningPlan(l1.next,l2);
return l1;
}else {
l2.next=trainningPlan(l1,l2.next);
return l2;
}
}
}
思路：先进行判空并处理，接着递归的添加下一个对应的结点即可。
时间复杂度O(n+m)
空间复杂度O(n+m)

0 赞同 0 条回复

黑键〰普通 2024年11月20日下午8:26

/**
* 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) {
if(l1 = null) return l2
if(l2 = null) return l1
let dummy = new ListNode()
let cur = dummy
let p1 = l1
let p2 = l2
while(p1 ! null || p2 ! null) {
if(p1 null) {
cur.next = p2
return dummy.next
}
if(p2 null) {
cur.next = p1
return dummy.next
}
if(p1.val <= p2.val) {
cur.next = p1
p1 = p1.next
} else {
cur.next = p2
p2 = p2.next
}
cur = cur.next
}
return dummy.next
};
思路：两个指针分别在两个链表上移动
时间复杂度O(N)
空间复杂度O(1)

0 赞同 0 条回复

🍊 普通 2024年11月20日下午8:20

归并
/**
* 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(), r = res;
while(l1 != null || l2 != null){
if(l1 null || (l2 != null && l2.val <= l1.val)){
r.next = l2;
r = r.next;
l2 = l2.next;
}
else{
r.next = l1;
r = r.next;
l1 = l1.next;
}
}
return res.next;
}
}

0 赞同 0 条回复

苯庸普通 2024年11月20日下午8:17

class Solution {
public ListNode trainningPlan(ListNode l1, ListNode l2) {
ListNode cur = new ListNode();
ListNode dummyHead = cur;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
cur.next = l1;
l1 = l1.next;
}else{
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
if(l1 null){
cur.next = l2;
}else{
cur.next = l1;
}
return dummyHead.next;
}
}
思路：依次遍历合并，最后判断l1、l2哪个为空就接上另一个
时间：o（n）
空间：o（1）

0 赞同 0 条回复

迢迢星野普通 2024年11月20日下午8:16

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

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

        return dummy.next;        
    }
}

创建虚拟头节点用于构建新链表，cur 指针用于遍历和构建新链表；
使用 while 循环判断 l1 和 l2 都不为空时，比较它们的节点值大小，小的节点则连接到新链表的后面，并将其对应指针前移，更新 cur 指针，使其指向新链表的最后一个节点，用于循环和后续连接剩余节点使用。
当 l1 和 l2 有一个链表不为空时，退出 while 循环，此时，将剩余的一个链表连接到新链表的尾部。
返回新链表的头节点 dummy.next 即可。

时间复杂度：O(m + n)，遍历了两个链表。
空间复杂度：O(1)，使用了常数级的额外空间。

0 赞同 0 条回复

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

共以下 55 个回答

思路

代码

Definition for singly-linked list.

class ListNode:

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. 合并两个排序的链表

共以下 55 个回答

思路

代码

Definition for singly-linked list.

class ListNode:

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

# 回答此问题 取消回复

# 回答此问题取消回复