21. 合并两个有序链表
3 min
题目
解法：双指针
思路
核心思想是使用双指针迭代比较节点值，每次选择较小值的节点接入新链表。
正确性在于：由于两个链表本身有序，每次选择当前最小节点能保证全局有序性；当一个链表遍历完后，另一个链表的剩余部分必然大于已合并部分且自身有序，直接拼接不会破坏顺序。
- Step 1: 创建虚拟头节点dummy和尾指针p
- Step 2: 循环比较list1和list2的当前节点值
- Step 3: 将较小值的节点接入p的next并移动对应链表指针
- Step 4: 将p移动到新接入的节点
- Step 5: 循环结束后将剩余非空链表直接接入尾部
复杂度
- 时间复杂度: ，其中和为两个链表的长度。每个节点仅被访问一次。
- 空间复杂度: ，仅使用常数空间存储虚拟头节点和指针。
代码
/**
* 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* p = dummy;
while(list1 != NULL && list2 != NULL)
{
if(list1->val < list2->val)
{
dummy->next = list1;
list1 = list1->next;
}
else
{
dummy->next = list2;
/**
* 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* p = dummy;
while(list1 != NULL && list2 != NULL)
{
if(list1->val < list2->val)
{
dummy->next = list1;
list1 = list1->next;
}
else
{
dummy->next = list2;
list2 = list2->next;
}
dummy = dummy->next;
}
if(list1 != NULL)
{
dummy->next = list1;
}
if(list2 != NULL)
{
dummy->next = list2;
}
return p->next;
}
};