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

力扣最热一百题——合并两个有序链表

news 来源：原创 2024/9/19 18:06:07

题目链接：21. 合并两个有序链表 - 力扣（LeetCode）

题目描述

示例

提示：

解法一：比大小放入

Java写法：

运行时间以及复杂度

C++写法：

运行时间以及复杂度

总结

题目链接：21. 合并两个有序链表 - 力扣（LeetCode）

注：下述题目描述和示例均来自力扣

题目描述

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

示例

示例 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 均按 非递减顺序 排列

解法一：比大小放入

初始化哨兵节点：
- 创建一个哨兵节点（dummy node），其next指针指向null。这个哨兵节点将作为新链表的临时头部，这样做的好处是可以方便地在链表头部添加元素，而不需要特殊处理头节点为空的情况。
双指针迭代：
- 使用两个指针list1和list2分别指向两个待合并链表的头部。
- 遍历这两个链表，直到其中一个链表被完全遍历（即其指针为null）。
- 在每次迭代中，比较list1和list2当前指向的节点的值：
  - 如果list1的值较小或等于list2的值（由于题目中可能有重复元素，所以这里使用了小于等于），则将list1的当前节点连接到新链表的末尾（即哨兵节点的next指向的节点之后），并将list1的指针向后移动一位。
  - 否则，将list2的当前节点连接到新链表的末尾，并将list2的指针向后移动一位。
- 同时，更新新链表的末尾指针（即current指针），使其指向新添加的节点。
处理剩余链表：
- 当其中一个链表被完全遍历后，如果另一个链表还有剩余节点（即其指针不为null），则将这个剩余链表直接连接到新链表的末尾。
- 这是因为剩余的链表已经是有序的，所以可以直接添加而不需要进一步排序或比较。
返回合并后的链表：
- 遍历结束后，新链表的头部就是哨兵节点的next指针所指向的节点（因为哨兵节点只是为了方便操作而创建的，并不属于实际的合并结果）。
- 所以，返回哨兵节点的next指针即可得到合并后的有序链表。

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 mergeTwoLists(ListNode list1, ListNode list2) {  // 创建一个哨兵节点，方便处理头节点  ListNode sentinel = new ListNode(0);  ListNode current = sentinel;  while (list1 != null && list2 != null) {  if (list1.val < list2.val) {  current.next = list1;  list1 = list1.next;  } else {  current.next = list2;  list2 = list2.next;  }  current = current.next;  }  // 如果list1或list2还有剩余节点，直接连接到结果链表的末尾  if (list1 != null) {  current.next = list1;  }  if (list2 != null) {  current.next = list2;  }  // 返回哨兵节点的下一个节点，即合并后的链表头节点  return sentinel.next;  }  
}

运行时间以及复杂度

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* mergeTwoLists(ListNode* list1, ListNode* list2) {  // 创建一个哨兵节点  ListNode* sentinel = new ListNode(0);  ListNode* current = sentinel;  // 使用双指针迭代合并两个链表  while (list1 != nullptr && list2 != nullptr) {  if (list1->val < list2->val) {  current->next = list1;  list1 = list1->next;  } else {  current->next = list2;  list2 = list2->next;  }  current = current->next;  }  // 处理剩余链表  if (list1 != nullptr) {  current->next = list1;  }  if (list2 != nullptr) {  current->next = list2;  }  // 返回合并后的链表头节点（哨兵节点的下一个节点）  ListNode* mergedHead = sentinel->next;  // 释放哨兵节点内存（可选，如果后续不再使用哨兵节点）  delete sentinel; // 注意：在实际应用中，可能需要保留哨兵节点以简化链表操作  // 但由于哨兵节点在函数返回后可能无法再被访问，因此通常不会在这里删除它  // 除非你确定合并后的链表将使用新的头节点进行管理，并且哨兵节点不再需要  // 由于通常哨兵节点是为了方便链表操作而引入的，并且会在函数外部进行管理，  // 因此这里我们不会删除哨兵节点，而是直接返回它指向的下一个节点作为合并后的链表头  return mergedHead;  // 注意：上面的delete sentinel;在实际情况下通常是不应该执行的，  // 因为哨兵节点是在函数内部创建的，并且其内存管理应该由调用者负责。  // 在这个例子中，我们直接返回了mergedHead，并没有删除哨兵节点。  }  
};  // 注意：在实际使用中，通常不会删除哨兵节点，因为它只是作为一个辅助节点来帮助我们构建新链表。  
// 调用者应该负责管理哨兵节点（尽管在这个特定的例子中，哨兵节点并没有被直接返回给调用者）。  
// 但是，由于哨兵节点的`next`指针指向了合并后的链表头节点，我们可以安全地返回`mergedHead`而不用担心哨兵节点的内存泄漏。

运行时间以及复杂度

总结

说点注意事项吧。

内存管理：在C++中，如果链表节点是动态分配的（如使用new关键字），则需要注意内存泄漏的问题。然而，在这个特定的例子中，我们并没有直接返回哨兵节点，而是返回了哨兵节点的下一个节点作为合并后的链表头。因此，哨兵节点的内存管理应由调用者负责，但在函数内部通常不会删除它，因为哨兵节点只是作为辅助节点使用。
链表头节点：合并后的链表头节点是哨兵节点的下一个节点，它在新链表中是第一个真正的数据节点。
链表遍历：在迭代过程中，我们实际上是在遍历两个链表，并通过比较来构建新的链表。当其中一个链表被完全遍历后，我们只需将另一个链表的剩余部分连接到新链表的末尾即可。
链表结构：合并后的链表仍然保持升序排列，且其节点值来自原始的两个链表。