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つの手はそれぞれ序列のトランプを持っていて、手の中の最小の点数を選ぶたびに、机の上に置いて、最後に彼らは下から上まで秩序正しく畳んでいました.では、片手を先に全部置いておけば、残りのカードをそのままテーブルの上に置くことができます.