题目描述
题目链接:21. Merge Two Sorted Lists
Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.
例子
例子 1
Input:
l1 = [1,2,4], l2 = [1,3,4]
Output:[1,1,2,3,4,4]
例子 2
Input:
l1 = [], l2 = []
Output:[]
例子 3
Input:
l1 = [], l2 = [0]
Output:[0]
Constraints
- The number of nodes in both lists is in the range
[0, 50]
.-100 <= Node.val <= 100
- Both
l1
andl2
are sorted in non-decreasing order.
解题思路
由于两个链表都已经排好序,所以只需要用两个指针指向两个链表,每次比较两个节点,并将当前节点指向较小的那一个(如果其中一个为空则指向另一个)即可。
代码如下:
/**
* 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) {
ListNode* dummy = new ListNode();
ListNode* curr = dummy;
while (l1 && l2) {
if (l1->val <= l2->val) {
curr->next = l1;
l1 = l1->next;
}
else {
curr->next = l2;
l2 = l2->next;
}
curr = curr->next;
}
if (!l1) {
curr->next = l2;
} else if (!l2) {
curr->next = l1;
}
return dummy->next;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1)
GitHub 代码同步地址: 21.MergeTwoSortedLists.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions