LeetCode 0021 - Merge Two Sorted Lists
# Hints
- 链表 + 水题 + 双指针扫描
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Easy |
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
# 题意
给定两个有序链表,要求将其中所有节点合并为一个新的有序链表。
# 题解
水题,双指针扫描即可。
我们同时从两个链表的表头出发,设两个指针为 ,根据 p->val
和 q->val
决定将何者放入新链表并递进即可。
细节问题:
注意特判其中一个或两个链表为空的情况。
注意可能其中一个指针到达表尾而另一个却没有,要特殊处理剩余部分。
# AC代码
/**
* 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 * l1, ListNode * l2) {
// 特判
if (l1 == nullptr && l2 == nullptr) {
return nullptr;
} else if (l1 == nullptr) {
return l2;
} else if (l2 == nullptr) {
return l1;
}
// 初始化
ListNode * head;
if (l1->val < l2->val) {
head = l1;
l1 = l1->next;
} else {
head = l2;
l2 = l2->next;
}
ListNode * l3 = head;
// 主循环
while (l1 != nullptr && l2 != nullptr) {
if (l1->val < l2->val) {
l3->next = l1;
l3 = l1;
l1 = l1->next;
} else {
l3->next = l2;
l3 = l2;
l2 = l2->next;
}
}
// 处理剩余部分
if (l1 != nullptr) {
l3->next = l1;
} else if (l2 != nullptr) {
l3->next = l2;
}
// 返回
return head;
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01