排序两个链表
思路:
每次对比两条链表的当前节点, 按适当顺序插入的同时需要注意一点
如果小的节点的接下来的值依旧小于大的节点, 那么需要继续往下遍历, 知道遇到一个节点大于大的节点
这样的话一次循环中就可以排序多个节点, 循环的次数就可以变少
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if (!l1 && l2) return l2;
if (!l2 && l1) return l1;
ListNode *smaller = l1->val > l2->val ?
l2 : l1;
ListNode *bigger = l1->val > l2->val ?
l1 : l2;
ListNode *result = smaller;
while (smaller && bigger) {
while (smaller->next && smaller->next->val < bigger->val)
smaller = smaller->next;
ListNode *tmps = smaller->next;
smaller->next = bigger;
smaller = bigger;
bigger = tmps;
}
return result;
}
};
|
采用了一次循环对比多个的算法, 每次循环之后不必再计算谁大谁小, 身份像开关一样会互换
但是代码复杂度增加了
结果:
emmmmm…, 预差有点大…
按理来说我觉得算法很好啊, 一次循环中排序了多个节点
每次循环后还不需要计算谁大谁小
分析一下4ms的算法:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* pre=new ListNode(0);
ListNode* crt=pre;
while(l1!=NULL && l2!=NULL){
if(l1->val<l2->val) {
crt->next=l1;
l1=l1->next;
}
else {
crt->next=l2;
l2=l2->next;
}
crt=crt->next;
}
crt->next=(l1==NULL)?l2:l1;
return pre->next;
}
};
|
emmmm…
他的思路很简单, 每次对比两个节点, 筛选出一个最小的
将筛选出节点的那条链接往下循环, 另外一条不变
但是时间比我少了很多, 我仔细思考了的算法反倒没有这种单纯的算法好
有点出乎意料和不服气…
@exprience:
我以后或许需要考虑 以循环次数换取减少循环复杂度 的做法了
这样的话我的每次循环尽量简单, 虽然次数变多了, 但是总体的效率可能还会有提升, 比如这次 = =