当前位置：首页 > article >正文

力扣题目解析--合并两个链表

article 2024/11/15 15:30:15

题目

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode*dummy=new ListNode(0);
        ListNode*current=dummy;
        while(list1&&list2){
            if(list1->val<list2->val){
                current->next=list1;
                list1=list1->next;
            }else{
                current->next=list2;
                list2=list2->next;
            }
            current=current->next;
        }
        if(list1){
            current->next=list1;
        }else{
            current->next=list2;
        }
        return dummy->next;
    }
};

写者心得

current = current->next;解释

示例

假设我们有两个链表：

list1: 1 -> 3 -> 5
list2: 2 -> 4 -> 6

合并过程如下：

初始化 dummy 和 current：
```
dummy -> null
current -> dummy
```
第一次循环：
- 比较 1 和 2，选择 1。
- 连接 1 到 current 的下一个位置。
- 移动 current 到 1。
```
dummy -> 1 -> null
current -> 1
```
第二次循环：
- 比较 3 和 2，选择 2。
- 连接 2 到 current 的下一个位置。
- 移动 current 到 2。
```
dummy -> 1 -> 2 -> null
current -> 2
```
第三次循环：
- 比较 3 和 4，选择 3。
- 连接 3 到 current 的下一个位置。
- 移动 current 到 3。
```
dummy -> 1 -> 2 -> 3 -> null
current -> 3
```
第四次循环：
- 比较 5 和 4，选择 4。
- 连接 4 到 current 的下一个位置。
- 移动 current 到 4。
```
dummy -> 1 -> 2 -> 3 -> 4 -> null
current -> 4
```
第五次循环：
- 比较 5 和 6，选择 5。
- 连接 5 到 current 的下一个位置。
- 移动 current 到 5。
```
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
current -> 5
```
第六次循环：
- 比较 null 和 6，选择 6。
- 连接 6 到 current 的下一个位置。
- 移动 current 到 6。
```
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
current -> 6
```
处理剩余节点：
- list1 已经为空，将 list2 剩余的部分连接到 current 的下一个位置。
- 由于 list2 也已经为空，所以不需要额外操作。

返回结果：

return dummy->next;

结果链表为：

1 -> 2 -> 3 -> 4 -> 5 -> 6

代码的逐行解释

创建虚拟头节点

        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;

ListNode* dummy = new ListNode(0);：创建一个虚拟头节点 dummy，初始化值为0，指针为nullptr。
ListNode* current = dummy;：创建一个指针 current，初始化指向 dummy。current 用于跟踪结果链表的当前末尾节点。

合并两个链表

        while (list1 && list2) {

while (list1 && list2)：当 list1 和 list2 都不为空时，进入循环。

选择较小节点

            if (list1->val < list2->val) {
                current->next = list1;
                list1 = list1->next;
            } else {
                current->next = list2;
                list2 = list2->next;
            }

if (list1->val < list2->val)：比较 list1 和 list2 当前节点的值。
- 如果 list1 的值小于 list2 的值：
  - current->next = list1;：将 list1 当前节点连接到 current 的下一个位置。
  - list1 = list1->next;：将 list1 指针移动到下一个节点。
- 否则：
  - current->next = list2;：将 list2 当前节点连接到 current 的下一个位置。
  - list2 = list2->next;：将 list2 指针移动到下一个节点。

更新 `current` 指针

            current = current->next;

current = current->next;：将 current 指针移动到刚刚连接的节点上，确保 current 始终指向结果链表的最后一个节点。

处理剩余节点

        if (list1) {
            current->next = list1;
        } else {
            current->next = list2;
        }

if (list1)：如果 list1 不为空：
- current->next = list1;：将 list1 剩余的部分连接到 current 的下一个位置。
else：如果 list1 为空（即 list2 不为空）：
- current->next = list2;：将 list2 剩余的部分连接到 current 的下一个位置。