C++で２つのリンクリストを、数値の大きさ順に１つにまとめたい

期待されているような、連結したリストが出力されません。

input l1[1,2,4]
      l2[1,3,4]

output "Time Limit Exceeded

expected [1,1,2,3,4,4]

###定義

C++
1/**
2 * Definition for singly-linked list.
3 * struct ListNode {
4 *     int val;
5 *     ListNode *next;
6 
7 *     ListNode() : val(0), next(nullptr) {}
8 *     ListNode(int x) : val(x), next(nullptr) {}
9 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
10 * };
11 */

###私の問題を含んだ回答

C++
1
2   ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
3        //2つの並べ替えられたリンクリストを、新しい並べ替えられたリストとして返します。 
4        ListNode *nodePtr=new ListNode;
5        while(l2!=NULL || l1!=NULL)
6        {       
7            if(l1==NULL){
8                nodePtr=l2;
9                l2=l2->next;   
10            }else if(l2==NULL){
11                nodePtr=l1;
12                l1=l1->next;
13            }else{
14                //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
15                if(l1->val <= l2->val){
16                    //l1の値の方が小さいので、nodePtrはl1に連結させる
17                    nodePtr=l1;
18                    //リスト1を次の要素に進める
19                    l1=l1->next;
20                }else{
21                    nodePtr=l1;
22                    l2=l2->next;  
23                }  
24            } 
25            nodePtr->next=nodePtr;
26        }   
27        return nodePtr;
28    }

###下記の模範解答も参考したのですが、私のコードとの違いがわかりません。
模範回答

C++
1    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
2            
3            ListNode *nodePtr;
4            if(l1==NULL){
5                return l2;
6            } else if(l2==NULL){
7                return l1;
8            }
9        
10            if(l1->val<=l2->val){
11                nodePtr=l1;
12                nodePtr->next=mergeTwoLists(l1->next,l2);
13            } else{
14                nodePtr=l2;
15                nodePtr->next=mergeTwoLists(l1,l2->next);
16            }
17            
18            return nodePtr;
19    }
20};

e-watt

2020/06/21 01:24

質問が不明なので感想を書きますが、ループの序盤でl1とl2の片方だけがNULLだったら、 num1やnum2の値はどうするんだろうと気になりました。

edoooooo

2020/06/21 02:18

感想をいただいた点を修正しました。もし引き続きアドバイスをいただけたらよろしくお願いします。

hope_mucci

2020/06/21 02:51

このリンクリストは循環されていないのが保証されているのでしょうか？

edoooooo

2020/06/21 03:09

すみません。循環するということがどのようなことかわかりませんでした。

edoooooo

2020/06/21 03:11

模範回答の中で、循環していないことを証明するようなコードはないように思ったのですが、どうでしょうか

edoooooo

2020/06/21 03:16

LeetCodeというプログラミング問題サイトで実行してるのですが、その開発環境によるエラーなのでしょうか？

hope_mucci

2020/06/21 03:27

リストの循環とは、ここでいうnextにリストの先頭アドレスが入るノードがあると終端がなくなりずっとぐるぐる回る状態を指します。まあ「ソートされている」と書かれているから循環していないと考えられます。

edoooooo

2020/06/21 03:29

ありがとうございます。この問題に使われている２つのリストは、 l1 [1,2,4] l2 [1,3,4] なので、循環はしていませんでした。

行動規範の内容に同意します

回答2件

ベストアンサー

ループで実現する場合は、先頭のノードと現在のノードのポインタを使用する必要があります。
nodePtrで連結対象のポインタをl1かl2に決定する方法は問題ないと思います。
nodePtrを決定した後に、先頭のノードと現在のノードのポインタの設定と返却をするようにすれば、今回の処理で動作します。

C++
1   ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
2
3        //2つの並べ替えられたリンクリストを、新しい並べ替えられたリストとして返します。 
4        ListNode *rootPtr=NULL; //★先頭のノードを保持する
5        ListNode *currentPtr;   //★現在のノードを保持する
6        ListNode *nodePtr;      //★l1かl2のどちらかを一時的に保持する
7
8        while(l2!=NULL || l1!=NULL)
9        {
10            //★この処理は不要
11            //if(nodePtr!=NULL){
12            //    nodePtr=nodePtr->next;
13            //}
14
15            //★nodePtrにl1かl2の連結したい側を設定（ここは修正なし）
16            if(l1==NULL){
17                nodePtr=l2;
18                l2=l2->next;
19
20            }else if(l2==NULL){
21                nodePtr=l1;
22                l1=l1->next;
23
24            }else{
25                //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
26                if(l1->val <= l2->val){
27                    //l1の値の方が小さいので、nodePtrはl1に連結させる
28                    nodePtr=l1; 
29                    //リスト1を次の要素に進める
30                    l1=l1->next;
31
32                }else{
33                    nodePtr=l2;
34                    l2=l2->next;
35                }
36
37            }
38            //★先頭のノードが未設定なら設定
39            if(rootPtr == NULL){
40                rootPtr=nodePtr;
41            }
42            //★現在のノードの次に連結する
43            else{
44                currentPtr->next=nodePtr;
45            }
46            //★現在のノードを次に移動する
47            currentPtr=nodePtr;
48        }
49        //★先頭のノードを返却する
50        return rootPtr;
51        //return nodePtr;
52    }