Code & Fun

打卡,第五天

今天偷个懒,找下自信先,做个Easy的题目——Merge Two Sorted List (我也没想到是这么简单的题目)

之前在 LintCode做个一个链表排序,也写过一篇blog
解这道题时用的是MergeSort去做.所以已经写过一次Merge Two Sorted List了,之前的写法是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
ListNode *mergeList(ListNode *l1,ListNode *l2){
if (!l1) return l2;
else if (!l2) return l1;
ListNode* ret = new ListNode(0);
ListNode*p = ret;
while(l1 && l2) {
if (l1->val > l2->val) {
ret->next = l2;
ret = ret->next;
l2 = l2->next;
} else {
ret->next = l1;
ret = ret->next;
l1 = l1->next;
}
}
ret->next = (l1)?l1:l2;
ret = p->next;
delete p;
return ret;
}

这次做一个小改进(可能时间复杂度上没有改进):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* head = new ListNode(0);
ListNode* ret = head;
while(l1 || l2) {
if ((l1 && l2 && l1->val > l2->val )|| !l1) {
head->next = l2;
head = head->next;
l2 = l2->next;
}else {
head->next = l1;
head = head->next;
l1 = l1->next;
}
}
head = ret->next;
delete ret;
return head;
}

恩,细细想想,这个思路效率可能跟慢,不过用在对数组的Merge的情况还是可以的(起码比较简洁)。


本文首发于Code & Fun