LeetCode Merge Two Sorted Lists 归并排序

浏览数：38 / 时间：2015年06月08日

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
12         if(l1==0)    return l2;
13         if(l2==0)    return l1;
14         ListNode *start=0,*end=0;
15         if(l1->val<l2->val){
16             start=end=l1;
17             l1=l1->next;
18         }
19         else{
20             start=end=l2;
21             l2=l2->next;
22         }
23         while(l1!=0&&l2!=0){
24             if(l1->val<l2->val){
25                 end->next=l1;
26                 l1=l1->next;
27             }
28             else{
29                 end->next=l2;
30                 l2=l2->next;
31             }
32             end=end->next;
33         }
34         if(l1==0)
35             end->next=l2;
36         else
37             end->next=l1;
38         return start;   
39     }
40 };

题意：将两个已有序的链表归并为一个有序的链表，并返回。

思路：就不用递归！第一个值先比较大小，将start指向小的那个，作为最后的返回地址。li不断和l2比较，每比较一次就将一个结点归到end指针的后面，end也是从start开始的。最后一定会将两个链表串在一起，并有序。比喻：两个手分别拿着已有序的扑克牌，每次挑出手中最小的点数，放在桌子上，最后他们就从下到上有序地叠在一起了。那么一只手先放光了，那么就可以把剩余的牌直接放桌子上了。

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

LeetCode Merge Two Sorted Lists 归并排序