teratail
回答率
85.30%
質問するログイン新規登録
トップに関する質問C++で２つのリンクリストを、数値の大きさ順に１つにまとめたい

編集履歴

質問編集履歴

16

発生するエラーの変更とコードの修正

2020/06/21 03:46

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -3,7 +3,7 @@
3
3
  input l1[1,2,4]
4
4
  l2[1,3,4]
5
5
 
6
- output [4]
6
+ output "Time Limit Exceeded
7
7
 
8
8
  expected [1,1,2,3,4,4]
9
9
  ```
@@ -28,7 +28,7 @@
28
28
 
29
29
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
30
30
  //2つの並べ替えられたリンクリストを、新しい並べ替えられたリストとして返します。
31
- ListNode *nodePtr;
31
+ ListNode *nodePtr=new ListNode;
32
32
  while(l2!=NULL || l1!=NULL)
33
33
  {
34
34
  if(l1==NULL){
@@ -41,14 +41,15 @@
41
41
  //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
42
42
  if(l1->val <= l2->val){
43
43
  //l1の値の方が小さいので、nodePtrはl1に連結させる
44
- nodePtr->next=l1;
44
+ nodePtr=l1;
45
45
  //リスト1を次の要素に進める
46
46
  l1=l1->next;
47
47
  }else{
48
- nodePtr->next=l1;
48
+ nodePtr=l1;
49
- l2=l2->next;
49
+ l2=l2->next;
50
- }
50
+ }
51
- }
51
+ }
52
+ nodePtr->next=nodePtr;
52
53
  }
53
54
  return nodePtr;
54
55
  }

15

コードを見やすく変更

2020/06/21 03:46

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -27,21 +27,16 @@
27
27
  ```C++
28
28
 
29
29
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
30
-
31
30
  //2つの並べ替えられたリンクリストを、新しい並べ替えられたリストとして返します。
32
31
  ListNode *nodePtr;
33
-
34
32
  while(l2!=NULL || l1!=NULL)
35
- {
33
+ {
36
-
37
34
  if(l1==NULL){
38
35
  nodePtr=l2;
39
- l2=l2->next;
36
+ l2=l2->next;
40
-
41
37
  }else if(l2==NULL){
42
38
  nodePtr=l1;
43
39
  l1=l1->next;
44
-
45
40
  }else{
46
41
  //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
47
42
  if(l1->val <= l2->val){
@@ -49,12 +44,10 @@
49
44
  nodePtr->next=l1;
50
45
  //リスト1を次の要素に進める
51
46
  l1=l1->next;
52
-
53
47
  }else{
54
48
  nodePtr->next=l1;
55
49
  l2=l2->next;
56
- }
50
+ }
57
-
58
51
  }
59
52
  }
60
53
  return nodePtr;

14

コードを改善しました。

2020/06/21 03:35

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -33,9 +33,6 @@
33
33
 
34
34
  while(l2!=NULL || l1!=NULL)
35
35
  {
36
- if(nodePtr!=NULL){
37
- nodePtr=nodePtr->next;
38
- }
39
36
 
40
37
  if(l1==NULL){
41
38
  nodePtr=l2;
@@ -49,12 +46,12 @@
49
46
  //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
50
47
  if(l1->val <= l2->val){
51
48
  //l1の値の方が小さいので、nodePtrはl1に連結させる
52
- nodePtr=l1;
49
+ nodePtr->next=l1;
53
50
  //リスト1を次の要素に進める
54
51
  l1=l1->next;
55
52
 
56
53
  }else{
57
- nodePtr=l2;
54
+ nodePtr->next=l1;
58
55
  l2=l2->next;
59
56
  }
60
57
 
@@ -62,7 +59,6 @@
62
59
  }
63
60
  return nodePtr;
64
61
  }
65
- };
66
62
  ```
67
63
  ###下記の模範解答も参考したのですが、私のコードとの違いがわかりません。
68
64
  模範回答

13

１つの問題の解決により質問を修正しました。

2020/06/21 03:34

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -1,9 +1,11 @@
1
- このようなエラーが出ます。
1
+ 期待されているような、連結したリストが出力されません。
2
2
  ```
3
- Line 30: Char 30: runtime error: member access within misaligned address 0x000000000001 for type 'ListNode', which requires 8 byte alignment (solution.cpp)
4
- 0x000000000001: note: pointer points here
3
+ input l1[1,2,4]
4
+ l2[1,3,4]
5
+
6
+ output [4]
7
+
5
- <memory cannot be printed>
8
+ expected [1,1,2,3,4,4]
6
- SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:39:30
7
9
  ```
8
10
 
9
11
  ###定義
@@ -24,37 +26,43 @@
24
26
  ###私の問題を含んだ回答
25
27
  ```C++
26
28
 
27
- ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
29
+ ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
28
30
 
29
31
  //2つの並べ替えられたリンクリストを、新しい並べ替えられたリストとして返します。
30
32
  ListNode *nodePtr;
31
33
 
32
34
  while(l2!=NULL || l1!=NULL)
33
35
  {
36
+ if(nodePtr!=NULL){
37
+ nodePtr=nodePtr->next;
38
+ }
39
+
34
40
  if(l1==NULL){
35
- nodePtr->next=l2;
41
+ nodePtr=l2;
36
42
  l2=l2->next;
37
43
 
38
44
  }else if(l2==NULL){
39
- nodePtr->next=l1;
45
+ nodePtr=l1;
40
46
  l1=l1->next;
41
47
 
42
48
  }else{
43
49
  //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
44
50
  if(l1->val <= l2->val){
45
51
  //l1の値の方が小さいので、nodePtrはl1に連結させる
46
- nodePtr->next=l1;
52
+ nodePtr=l1;
47
53
  //リスト1を次の要素に進める
48
54
  l1=l1->next;
49
55
 
50
56
  }else{
51
- nodePtr->next=l2;
57
+ nodePtr=l2;
52
58
  l2=l2->next;
53
59
  }
60
+
54
61
  }
55
62
  }
56
63
  return nodePtr;
57
64
  }
65
+ };
58
66
  ```
59
67
  ###下記の模範解答も参考したのですが、私のコードとの違いがわかりません。
60
68
  模範回答

12

コードを少し変更

2020/06/21 03:28

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -23,7 +23,8 @@
23
23
 
24
24
  ###私の問題を含んだ回答
25
25
  ```C++
26
+
26
- ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
27
+ ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
27
28
 
28
29
  //2つの並べ替えられたリンクリストを、新しい並べ替えられたリストとして返します。
29
30
  ListNode *nodePtr;
@@ -32,9 +33,11 @@
32
33
  {
33
34
  if(l1==NULL){
34
35
  nodePtr->next=l2;
36
+ l2=l2->next;
35
37
 
36
38
  }else if(l2==NULL){
37
39
  nodePtr->next=l1;
40
+ l1=l1->next;
38
41
 
39
42
  }else{
40
43
  //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入

11

レイアウトを整理

2020/06/21 03:04

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -6,7 +6,7 @@
6
6
  SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:39:30
7
7
  ```
8
8
 
9
- 定義
9
+ ###定義
10
10
  ```C++
11
11
  /**
12
12
  * Definition for singly-linked list.
@@ -21,6 +21,7 @@
21
21
  */
22
22
  ```
23
23
 
24
+ ###私の問題を含んだ回答
24
25
  ```C++
25
26
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
26
27
 

10

わかりやすくレイアウトを整理

2020/06/21 03:01

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -5,8 +5,9 @@
5
5
  <memory cannot be printed>
6
6
  SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:39:30
7
7
  ```
8
+
9
+ 定義
8
10
  ```C++
9
-
10
11
  /**
11
12
  * Definition for singly-linked list.
12
13
  * struct ListNode {
@@ -18,6 +19,9 @@
18
19
  * ListNode(int x, ListNode *next) : val(x), next(next) {}
19
20
  * };
20
21
  */
22
+ ```
23
+
24
+ ```C++
21
25
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
22
26
 
23
27
  //2つの並べ替えられたリンクリストを、新しい並べ替えられたリストとして返します。

9

自分の回答と、模範回答でも、変数名の統一化

2020/06/21 03:00

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -53,7 +53,7 @@
53
53
  ```C++
54
54
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
55
55
 
56
- ListNode *result;
56
+ ListNode *nodePtr;
57
57
  if(l1==NULL){
58
58
  return l2;
59
59
  } else if(l2==NULL){
@@ -61,14 +61,14 @@
61
61
  }
62
62
 
63
63
  if(l1->val<=l2->val){
64
- result=l1;
64
+ nodePtr=l1;
65
- result->next=mergeTwoLists(l1->next,l2);
65
+ nodePtr->next=mergeTwoLists(l1->next,l2);
66
66
  } else{
67
- result=l2;
67
+ nodePtr=l2;
68
- result->next=mergeTwoLists(l1,l2->next);
68
+ nodePtr->next=mergeTwoLists(l1,l2->next);
69
69
  }
70
70
 
71
- return result;
71
+ return nodePtr;
72
72
  }
73
73
  };
74
74
  ```

8

模範解答の追加

2020/06/21 02:59

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -48,5 +48,27 @@
48
48
  return nodePtr;
49
49
  }
50
50
  ```
51
-
51
+ ###下記の模範解答も参考したのですが、私のコードとの違いがわかりません。
52
+ 模範回答
53
+ ```C++
54
+ ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
55
+
56
+ ListNode *result;
57
+ if(l1==NULL){
52
- //
58
+ return l2;
59
+ } else if(l2==NULL){
60
+ return l1;
61
+ }
62
+
63
+ if(l1->val<=l2->val){
64
+ result=l1;
65
+ result->next=mergeTwoLists(l1->next,l2);
66
+ } else{
67
+ result=l2;
68
+ result->next=mergeTwoLists(l1,l2->next);
69
+ }
70
+
71
+ return result;
72
+ }
73
+ };
74
+ ```

7

コードの改善をしました。

2020/06/21 02:57

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -1,10 +1,12 @@
1
+ このようなエラーが出ます。
2
+ ```
3
+ Line 30: Char 30: runtime error: member access within misaligned address 0x000000000001 for type 'ListNode', which requires 8 byte alignment (solution.cpp)
4
+ 0x000000000001: note: pointer points here
5
+ <memory cannot be printed>
1
- ### LeetCodeというサイトで、プログラミングの問題を説いているのですが、採点結果が、Time Limit Exceededとなります。
6
+ SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:39:30
7
+ ```
8
+ ```C++
2
9
 
3
- どうすれば解決すると思われますか？
4
-
5
- ### 該当のソースコード
6
-
7
- ```C++
8
10
  /**
9
11
  * Definition for singly-linked list.
10
12
  * struct ListNode {
@@ -16,11 +18,9 @@
16
18
  * ListNode(int x, ListNode *next) : val(x), next(next) {}
17
19
  * };
18
20
  */
19
- class Solution {
20
- public:
21
- ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
21
+ ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
22
22
 
23
- //2つの並べ替えられたリンクリストをマージし、新しい並べ替えられたリストとして返します。 新しいリストは、最初の2つのリストのノードをつなぎ合わせて作成する必要があります。
23
+ //2つの並べ替えられたリンクリストを、新しい並べ替えられたリストとして返します。
24
24
  ListNode *nodePtr;
25
25
 
26
26
  while(l2!=NULL || l1!=NULL)
@@ -33,19 +33,20 @@
33
33
 
34
34
  }else{
35
35
  //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
36
- if(l1->val >= l2->val){
36
+ if(l1->val <= l2->val){
37
+ //l1の値の方が小さいので、nodePtrはl1に連結させる
38
+ nodePtr->next=l1;
39
+ //リスト1を次の要素に進める
40
+ l1=l1->next;
41
+
42
+ }else{
37
43
  nodePtr->next=l2;
38
- //リスト２を次の要素に進める
39
- l2=l2->next;
44
+ l2=l2->next;
40
-
41
- }else if(l1->val <= l2->val){
42
- nodePtr->next=l1;
43
- l1=l1->next;
44
45
  }
45
46
  }
46
47
  }
47
-
48
48
  return nodePtr;
49
49
  }
50
- };
51
- ```
50
+ ```
51
+
52
+ //

6

質問の修正

2020/06/21 02:53

投稿

edoooooo
edoooooo

スコア478

title CHANGED
@@ -1,1 +1,1 @@
1
- C++で２つのリンクリストを、数値の大きさ順に１つにまとめる。
1
+ C++で２つのリンクリストを、数値の大きさ順に１つにまとめたい
body CHANGED
File without changes

5

コードを改善しました。

2020/06/21 02:47

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -21,9 +21,7 @@
21
21
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
22
22
 
23
23
  //2つの並べ替えられたリンクリストをマージし、新しい並べ替えられたリストとして返します。 新しいリストは、最初の2つのリストのノードをつなぎ合わせて作成する必要があります。
24
- ListNode *nodePtr=new ListNode;
24
+ ListNode *nodePtr;
25
- int num1 , num2;
26
- bool again=true;
27
25
 
28
26
  while(l2!=NULL || l1!=NULL)
29
27
  {

4

コードを改善しました。

2020/06/21 02:46

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -20,44 +20,29 @@
20
20
  public:
21
21
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
22
22
 
23
+ //2つの並べ替えられたリンクリストをマージし、新しい並べ替えられたリストとして返します。 新しいリストは、最初の2つのリストのノードをつなぎ合わせて作成する必要があります。
23
- ListNode *nodePtr;
24
+ ListNode *nodePtr=new ListNode;
24
25
  int num1 , num2;
25
26
  bool again=true;
26
27
 
27
28
  while(l2!=NULL || l1!=NULL)
28
29
  {
29
- if(l1!=NULL){
30
+ if(l1==NULL){
30
- num1=l1->val;
31
+ nodePtr->next=l2;
31
- }
32
32
 
33
- if(l2!=NULL){
33
+ }else if(l2==NULL){
34
- num2=l2->val;
34
+ nodePtr->next=l1;
35
- }
36
35
 
37
- //１と２の連結したものをリスト３にいれる
38
- //1つめの要素
39
- if(nodePtr==NULL){
40
-
41
- if(num1>=num2){
42
- nodePtr=new ListNode(num2);
43
- }else{
44
- nodePtr=new ListNode(num1);
45
- }
46
- //１つめ以降のリスト
47
36
  }else{
48
- //次の要素に進む
49
- nodePtr=nodePtr->next;
50
-
51
- if(nodePtr!=NULL){
52
- //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
37
+ //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
53
- if(num1>=num2 || l1==NULL){ //←修正
38
+ if(l1->val >= l2->val){
54
- nodePtr->val=num2;
39
+ nodePtr->next=l2;
55
- //リスト２を次の要素に進める
40
+ //リスト２を次の要素に進める
56
- l2=l2->next;
41
+ l2=l2->next;
42
+
57
- }else if(num2<num1 || l2==NULL){ //←修正
43
+ }else if(l1->val <= l2->val){
58
- nodePtr->val=num1;
44
+ nodePtr->next=l1;
59
- l1=l1->next;
45
+ l1=l1->next;
60
- }
61
46
  }
62
47
  }
63
48
  }

3

アドバイスいただいた部分のコードを修正しました。

2020/06/21 02:40

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -1,7 +1,6 @@
1
1
  ### LeetCodeというサイトで、プログラミングの問題を説いているのですが、採点結果が、Time Limit Exceededとなります。
2
-
3
- 新しいリストは、最初の2つのリストのノードをつなぎ合わせて作成する必要があります。
4
2
 
3
+ どうすれば解決すると思われますか？
5
4
 
6
5
  ### 該当のソースコード
7
6
 
@@ -51,11 +50,11 @@
51
50
 
52
51
  if(nodePtr!=NULL){
53
52
  //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
54
- if(num1>=num2){
53
+ if(num1>=num2 || l1==NULL){ //←修正
55
54
  nodePtr->val=num2;
56
55
  //リスト２を次の要素に進める
57
56
  l2=l2->next;
58
- }else{
57
+ }else if(num2<num1 || l2==NULL){ //←修正
59
58
  nodePtr->val=num1;
60
59
  l1=l1->next;
61
60
  }

2

コードを少し変更

2020/06/21 02:17

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -25,7 +25,7 @@
25
25
  int num1 , num2;
26
26
  bool again=true;
27
27
 
28
- while(l2!=NULL && l1!=NULL)
28
+ while(l2!=NULL || l1!=NULL)
29
29
  {
30
30
  if(l1!=NULL){
31
31
  num1=l1->val;

1

問題の変更

2020/06/20 19:57

投稿

edoooooo
edoooooo

スコア478

title CHANGED
File without changes
body CHANGED
@@ -1,17 +1,8 @@
1
- ### 2つの並べ替えられたリンクリストをマージし、新しい並べ替えられたリストとして返したい。
1
+ ### LeetCodeというサイトで、プログラミングの問題を説いているのですが、採点結果が、Time Limit Exceededとなります。
2
2
 
3
3
  新しいリストは、最初の2つのリストのノードをつなぎ合わせて作成する必要があります。
4
- そこでこのようなエラーが出ます。
5
4
 
6
- ### エラー
7
- ```
8
- Line 77: Char 22: runtime error: member access within misaligned address 0xf3f3f3f8f1f1f1f1 for type 'const ListNode', which requires 8 byte alignment (_Serializer_.cpp)
9
- 0xf3f3f3f8f1f1f1f1: note: pointer points here
10
- <memory cannot be printed>
11
- SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior _Serializer_.cpp:86:22
12
- ```
13
5
 
14
-
15
6
  ### 該当のソースコード
16
7
 
17
8
  ```C++
@@ -34,7 +25,7 @@
34
25
  int num1 , num2;
35
26
  bool again=true;
36
27
 
37
- while(l2==NULL && l1==NULL)
28
+ while(l2!=NULL && l1!=NULL)
38
29
  {
39
30
  if(l1!=NULL){
40
31
  num1=l1->val;