系列专栏
《分治》
《模拟》
《Linux》
目录
1、题目链接
2、题目介绍
3、解法（双指针）
4、代码
1、题目链接
21. 合并两个有序链表 - 力扣（LeetCode）
2、题目介绍
3、解法（双指针）
推荐一篇题解题解 - 力扣（LeetCode）
- 解决方法：
- 使用一个伪头节点来简化边界条件的处理，特别是在插入第一个节点时。这避免了处理空链表或只有一个元素的特殊情况。
- 使用一个指针
tmp来遍历新链表，并始终保持它指向新链表的最后一个节点，以便于进行尾插操作。- 遍历两个给定的链表
list1和list2，比较当前节点的值，将较小的节点插入到新链表中，并移动相应链表的指针到下一个节点。- 当其中一个链表遍历完毕后，将另一个链表剩余的节点直接连接到新链表的末尾。
- 代码实现：
- 初始化伪头节点
head和临时指针tmp。- 使用
while循环遍历两个链表，直到其中一个链表为空。
- 在循环内部，比较
list1和list2当前节点的值。- 将值较小的节点插入到新链表中（即设置
tmp->next），并移动对应链表的指针。- 移动
tmp指针到新链表的最后一个节点。- 使用两个额外的
while循环来处理剩余的链表（如果有的话）。由于已经遍历过两个链表的一部分或全部，这两个循环中至多有一个会执行。
- 这两个循环的目的是将剩余链表的所有节点连接到新链表的末尾。
- 返回新链表的头节点（即
head->next，因为head是一个伪头节点）。细节很重要！！！
4、代码
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* head = new ListNode(0);//初始化伪头节点，便于遍历和返回ListNode* tmp = head;//在新链表中，指向最后一个结点，便于实现尾插while (list1 != nullptr && list2 != nullptr){if (list1->val < list2->val){tmp->next = list1;list1 = list1->next;}else {tmp->next = list2;list2 = list2->next;}tmp = tmp->next;}//tmp->next = list1 != nullptr ? list1 : list2;while (list1 != NULL){tmp->next = list1;list1 = list1->next;tmp = tmp->next;}while (list2 != NULL){tmp->next = list2;list2 = list2->next;tmp = tmp->next;}return head->next;//返回真正的头节点}};
