LeetCode Merge Two Sorted Lists集計ソート
5150 ワード
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 };
問題:2つの秩序化されたチェーンテーブルを1つの秩序化されたチェーンテーブルにまとめ、返します.
考え方:再帰する必要はありません!最初の値はまずサイズを比較し、startを小さいものに指し、最後の戻りアドレスとします.Liはl 2と絶えず比較し,比較するたびに1つのノードをendポインタの後ろに帰し,endもstartから始まる.最後に必ず2つのチェーンテーブルをつなぎ、秩序正しくします.2つの手はそれぞれ序列のトランプを持っていて、手の中の最小の点数を選ぶたびに、机の上に置いて、最後に彼らは下から上まで秩序正しく畳んでいました.では、片手を先に全部置いておけば、残りのカードをそのままテーブルの上に置くことができます.