发布时间:2023-10-03 12:30
原题连接: Leetcode 21. Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1
and list2
.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Constraints:
先建立一个虚拟头结点prehead,和一个指向虚拟头结点的指针prev。返回的时候返回prehead->head就可以,能减少很多麻烦的边界问题。
两个指针遍历两个链表。每次选择关键字小的结点接到prev上即可。
注意最后需要扫尾,把循环结束没遍历完的链表的余下部分直接接上去。
这个扫尾的思想用的太多了,类似于归并排序
/**
* 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) {
// 创建虚拟头结点prehead, 值为-1 prev为指向虚拟头结点的指针
ListNode* preHead = new ListNode(-1);
ListNode* prev = preHead;
// 双指针遍历两个链表
while(list1 != nullptr && list2 != nullptr){
// 找到小的结点
if(list1->val < list2->val){
prev->next = list1;
list1 = list1->next;
} else {
prev->next = list2;
list2 = list2->next;
}
prev = prev->next;
}
// 扫尾
prev->next = (list1 == nullptr ? list2 : list1);
return preHead->next;
}
};