系列专栏
《分治》
《模拟》
《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;//返回真正的头节点}};