此题不难。需要注意:
1) 当输入有空链表时的情况;
2) 当输入的两个链表长度不一致的情况。
#include <iostream>
using namespace std;
//Definition for singly-linked list.
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (l1==NULL) return l2;
if (l2==NULL) return l1;
ListNode* head;
if (l1->val <= l2->val) {
head = new ListNode(l1->val);
l1=l1->next;
}else {
head = new ListNode(l2->val);
l2=l2->next;
}
ListNode *temp=head;
while ((l1 || l2)) {
if ((!l2) || (l1&&(l1->val <= l2->val))) {
temp->next=new ListNode(l1->val);
l1=l1->next;
}
else if ((!l1) || (l2&&(l2->val <= l1->val))) {
temp->next=new ListNode(l2->val);
l2=l2->next;
}
temp=temp->next;
}
return head;
}
int main()
{
ListNode a1(1), a2(2), a3(4);
a1.next=&a2;
a2.next=&a3;
a3.next=NULL;
cout<<a1.val<<" ";
cout<<a1.next->val<<" ";
cout<<a1.next->next->val<<endl;
ListNode b1(1), b2(3), b3(4);
b1.next=&b2;
b2.next=&b3;
b3.next=NULL;
cout<<b1.val<<" ";
cout<<b1.next->val<<" ";
cout<<b1.next->next->val<<endl;
ListNode* c=mergeTwoLists(&a1, &b1);
while(c) {
cout<<c->val<<" "<<endl;
c=c->next;
}
return 0;
}
看到Leetcode网上贴了另一种做法,
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode dummy(INT_MIN);
ListNode *tail = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
tail->next = l1;
l1 = l1->next;
} else {
tail->next = l2;
l2 = l2->next;
}
tail = tail->next;
}
tail->next = l1 ? l1 : l2;
return dummy.next;
}
感觉有点意思,不过这个解法把返回的链表跟l1或l2的一部分合在一起,不知道符合要求否。