LCR 142. 训练计划 IV

给定两个以 有序链表 形式记录的训练计划 l1、l2，分别记录了两套核心肌群训练项目编号，请合并这两个训练计划，按训练项目编号升序记录于链表并返回。

注意：新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

java

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

java

输入：l1 = [], l2 = []
输出：[]

示例 3：

java

输入：l1 = [], l2 = [0]
输出：[0]

提示：

0 <= 链表长度 <= 1000

解

首先题目给出了链表结构如下：

java

1
2
3
4
5
6
7 * 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; }

所以我们首先可以先写出比较链表里元素的代码

java

1
2
3
4
5
6
7
8
9
10ListNode linked = new ListNode();
if(l1 <= l2){
	linked.val = l1;
	l1 = l1.next;
}else{
	linked.val = l2;
	l2 = l2.next
}
linked = linked.next

这样我们就完成了一个简单的判断，判断链表里元素的大小并向后移动，但是我们发现似乎缺一个合适的循环

我们仔细想一想，如果某个链表后续没有了元素为空，那么再使用.val访问时，是不是就会爆空指针异常，所以我们需要确保l1和l2都是不为空的，因此循环条件我们就推导出来了

while(l1.next != null && l2.next!= null)

但是一方为空就停止了循环，那另一方不为空的链表怎么办呢？

有题目我们得到两个链表都是升序链表，因此一方为空，直接把不为空的一方插到结果的后边即可

·current.next = l1 == null ? l2 : l1;·

但是他们两个链表有没有可能一起为空呢？

答案是：不可能，因为我们第一个判断条件是l1 <= l2，因此就是两个一模一样的链表进行比较，也会有一方先变成空

大家有没有注意到，上一个代码块中的代码变成了current而不是我们第一个代码快所定义的linked，这是因为我们还需要一个额外操作ListNode current = linked;定义一个指针，向前移动，而不是使用我们最初定义的链表，防止我们找不到头节点

因此代码如下：

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29/**
 * 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 linked = new ListNode(0);
        ListNode current = linked;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        current.next = l1 == null ? l2 : l1;
        return linked.next;
    }
}

诶自己想一想，这一题是不是还可以用递归进行解答呢？

上面我们提到过，一方为空，答案拼接上另一方即可，那么递归的结束语句这不是就有了吗？

java

1
2
3
4
5
6
7        if(l1 == null){
            return l2;
        }
        if(l2 == null){
            return l1;
        }

假设我们有以下两个链表：

l1 = [1, 2, 4]
l2 = [1, 3, 4]

递归的过程如下：

第一层递归：
- trainningPlan(l1 = [1, 2, 4], l2 = [1, 3, 4])
- 比较 l1.val (1) 和 l2.val (1)，它们相等，选择 l1
- 然后递归调用 trainningPlan(l1.next, l2) = trainningPlan([2, 4], [1, 3, 4])
第二层递归：
- trainningPlan(l1 = [2, 4], l2 = [1, 3, 4])
- 比较 l1.val (2) 和 l2.val (1)，选择 l2
- 然后递归调用 trainningPlan(l1, l2.next) = trainningPlan([2, 4], [3, 4])
第三层递归：
- trainningPlan(l1 = [2, 4], l2 = [3, 4])
- 比较 l1.val (2) 和 l2.val (3)，选择 l1
- 然后递归调用 trainningPlan(l1.next, l2) = trainningPlan([4], [3, 4])。
第四层递归：
- trainningPlan(l1 = [4], l2 = [3, 4])
- 比较 l1.val (4) 和 l2.val (3)，选择 l2
- 然后递归调用 trainningPlan(l1, l2.next) = trainningPlan([4], [4])
第五层递归：
- trainningPlan(l1 = [4], l2 = [4])
- 比较 l1.val (4) 和 l2.val (4)，它们相等，选择 l1。
- 然后递归调用 trainningPlan(l1.next, l2) = trainningPlan([], [4])
第六层递归：
- trainningPlan(l1 = [], l2 = [4])
- l1 为空，返回 l2（即 [4]）

回溯阶段：

递归开始回溯，每一层都会将当前选择的节点（l1 或 l2）的 .next 连接到递归返回的结果，形成最终的链表。

第六层回溯：
- 返回 [4]。
第五层回溯：
- l1 = [4]，将其 next 指向返回的 [4]，所以此时返回的链表是 [4, 4]
第四层回溯：
- l2 = [3]，将其 next 指向返回的 [4, 4]，所以此时返回的链表是 [3, 4, 4]
第三层回溯：
- l1 = [2]，将其 next 指向返回的 [3, 4, 4]，所以此时返回的链表是 [2, 3, 4, 4]
第二层回溯：
- l2 = [1]，将其 next 指向返回的 [2, 3, 4, 4]，所以此时返回的链表是 [1, 2, 3, 4, 4]
第一层回溯：
- l1 = [1]，将其 next 指向返回的 [1, 2, 3, 4, 4]，最终返回的链表是 [1, 1, 2, 3, 4, 4]

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29/**
 * 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;
        }
       if(l1.val <= l2.val){
            l1.next = trainningPlan(l1.next,l2);
            return l1;
       }else{
            l2.next=trainningPlan(l1,l2.next);
            return l2;
       }
    }
}

LCR 142. 训练计划 IV

解

回溯阶段：

评论 (0)

还没有评论