题目描述
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
样例
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
算法1
重点在于不使用额外空间
那么就逐个比较两个链表当前值
1 如果链表1节点值小于链表2节点值 就保留该值 链表1当前检查索引指向下一个链表节点
2 如果链表1节点值大于链表2节点值 交换两链表值后，链表1当前检查索引指向下一个链表节点。同时要保证链表2的升序
C++ 代码
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* head1 = l1;
ListNode* head2 = l2;
while (l1 != NULL && l2 != NULL) {
if (l1->val > l2->val) {
swap(l1->val, l2->val);
while (l2 != NULL && l2->next != NULL && l2->val > l2->next->val) {
swap(l2->val, l2->next->val);
l2 = l2->next;
}
l2 = head2;
if (l1->next != NULL)
l1 = l1->next;
else
break;
}
else {
if (l1->next != NULL)
l1 = l1->next;
else
break;
}
}
if(l1 != NULL){
while (l1->next != NULL) {
l1 = l1->next;
}
l1->next = head2;
}
else {
return head2;
}
return head1;
}
};
算法2
投机取巧办法 转化成数组后 再转回链表
C++ 代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1==NULL) return l2;
if(l2 == NULL) return l1;
vector<int> v;
ListNode* p = l1;
while(p!=NULL){
v.push_back(p->val);
p = p->next;
}
p = l2;
while(p!=NULL){
v.push_back(p->val);
p = p->next;
}
sort(v.begin(),v.end());
p =l1; int idx = 0;
while(p != NULL){
p->val = v[idx];
idx++;
if(p->next == NULL) break;
p=p->next;
}
if(p != NULL)
p->next = l2;
p =l2;
while(p != NULL){
p->val = v[idx];
idx++;
if(p->next == NULL) break;
p=p->next;
}
return l1;
}
};
