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

編集履歴

質問編集履歴

16

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

2020/06/21 03:46

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -8,7 +8,7 @@
8
8
 
9
9
 
10
10
 
11
- output [4]
11
+ output "Time Limit Exceeded
12
12
 
13
13
 
14
14
 
@@ -58,7 +58,7 @@
58
58
 
59
59
  //2つの並べ替えられたリンクリストを、新しい並べ替えられたリストとして返します。
60
60
 
61
- ListNode *nodePtr;
61
+ ListNode *nodePtr=new ListNode;
62
62
 
63
63
  while(l2!=NULL || l1!=NULL)
64
64
 
@@ -84,7 +84,7 @@
84
84
 
85
85
  //l1の値の方が小さいので、nodePtrはl1に連結させる
86
86
 
87
- nodePtr->next=l1;
87
+ nodePtr=l1;
88
88
 
89
89
  //リスト1を次の要素に進める
90
90
 
@@ -92,13 +92,15 @@
92
92
 
93
93
  }else{
94
94
 
95
- nodePtr->next=l1;
95
+ nodePtr=l1;
96
96
 
97
- l2=l2->next;
97
+ l2=l2->next;
98
98
 
99
- }
99
+ }
100
100
 
101
- }
101
+ }
102
+
103
+ nodePtr->next=nodePtr;
102
104
 
103
105
  }
104
106
 

15

コードを見やすく変更

2020/06/21 03:46

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -56,35 +56,25 @@
56
56
 
57
57
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
58
58
 
59
-
60
-
61
59
  //2つの並べ替えられたリンクリストを、新しい並べ替えられたリストとして返します。
62
60
 
63
61
  ListNode *nodePtr;
64
62
 
65
-
66
-
67
63
  while(l2!=NULL || l1!=NULL)
68
64
 
69
- {
65
+ {
70
-
71
-
72
66
 
73
67
  if(l1==NULL){
74
68
 
75
69
  nodePtr=l2;
76
70
 
77
- l2=l2->next;
71
+ l2=l2->next;
78
-
79
-
80
72
 
81
73
  }else if(l2==NULL){
82
74
 
83
75
  nodePtr=l1;
84
76
 
85
77
  l1=l1->next;
86
-
87
-
88
78
 
89
79
  }else{
90
80
 
@@ -100,17 +90,13 @@
100
90
 
101
91
  l1=l1->next;
102
92
 
103
-
104
-
105
93
  }else{
106
94
 
107
95
  nodePtr->next=l1;
108
96
 
109
97
  l2=l2->next;
110
98
 
111
- }
99
+ }
112
-
113
-
114
100
 
115
101
  }
116
102
 

14

コードを改善しました。

2020/06/21 03:35

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -68,12 +68,6 @@
68
68
 
69
69
  {
70
70
 
71
- if(nodePtr!=NULL){
72
-
73
- nodePtr=nodePtr->next;
74
-
75
- }
76
-
77
71
 
78
72
 
79
73
  if(l1==NULL){
@@ -100,7 +94,7 @@
100
94
 
101
95
  //l1の値の方が小さいので、nodePtrはl1に連結させる
102
96
 
103
- nodePtr=l1;
97
+ nodePtr->next=l1;
104
98
 
105
99
  //リスト1を次の要素に進める
106
100
 
@@ -110,7 +104,7 @@
110
104
 
111
105
  }else{
112
106
 
113
- nodePtr=l2;
107
+ nodePtr->next=l1;
114
108
 
115
109
  l2=l2->next;
116
110
 
@@ -125,8 +119,6 @@
125
119
  return nodePtr;
126
120
 
127
121
  }
128
-
129
- };
130
122
 
131
123
  ```
132
124
 

13

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

2020/06/21 03:34

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -1,14 +1,18 @@
1
- このようなエラーが出ます。
1
+ 期待されているような、連結したリストが出力されません。
2
2
 
3
3
  ```
4
4
 
5
- Line 30: Char 30: runtime error: member access within misaligned address 0x000000000001 for type 'ListNode', which requires 8 byte alignment (solution.cpp)
5
+ input l1[1,2,4]
6
6
 
7
- 0x000000000001: note: pointer points here
7
+ l2[1,3,4]
8
8
 
9
- <memory cannot be printed>
10
9
 
10
+
11
+ output [4]
12
+
13
+
14
+
11
- SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:39:30
15
+ expected [1,1,2,3,4,4]
12
16
 
13
17
  ```
14
18
 
@@ -50,7 +54,7 @@
50
54
 
51
55
 
52
56
 
53
- ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
57
+ ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
54
58
 
55
59
 
56
60
 
@@ -64,9 +68,17 @@
64
68
 
65
69
  {
66
70
 
71
+ if(nodePtr!=NULL){
72
+
73
+ nodePtr=nodePtr->next;
74
+
75
+ }
76
+
77
+
78
+
67
79
  if(l1==NULL){
68
80
 
69
- nodePtr->next=l2;
81
+ nodePtr=l2;
70
82
 
71
83
  l2=l2->next;
72
84
 
@@ -74,7 +86,7 @@
74
86
 
75
87
  }else if(l2==NULL){
76
88
 
77
- nodePtr->next=l1;
89
+ nodePtr=l1;
78
90
 
79
91
  l1=l1->next;
80
92
 
@@ -88,7 +100,7 @@
88
100
 
89
101
  //l1の値の方が小さいので、nodePtrはl1に連結させる
90
102
 
91
- nodePtr->next=l1;
103
+ nodePtr=l1;
92
104
 
93
105
  //リスト1を次の要素に進める
94
106
 
@@ -98,11 +110,13 @@
98
110
 
99
111
  }else{
100
112
 
101
- nodePtr->next=l2;
113
+ nodePtr=l2;
102
114
 
103
115
  l2=l2->next;
104
116
 
105
117
  }
118
+
119
+
106
120
 
107
121
  }
108
122
 
@@ -111,6 +125,8 @@
111
125
  return nodePtr;
112
126
 
113
127
  }
128
+
129
+ };
114
130
 
115
131
  ```
116
132
 

12

コードを少し変更

2020/06/21 03:28

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -48,7 +48,9 @@
48
48
 
49
49
  ```C++
50
50
 
51
+
52
+
51
- ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
53
+ ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
52
54
 
53
55
 
54
56
 
@@ -66,11 +68,15 @@
66
68
 
67
69
  nodePtr->next=l2;
68
70
 
71
+ l2=l2->next;
72
+
69
73
 
70
74
 
71
75
  }else if(l2==NULL){
72
76
 
73
77
  nodePtr->next=l1;
78
+
79
+ l1=l1->next;
74
80
 
75
81
 
76
82
 

11

レイアウトを整理

2020/06/21 03:04

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -14,7 +14,7 @@
14
14
 
15
15
 
16
16
 
17
- 定義
17
+ ###定義
18
18
 
19
19
  ```C++
20
20
 
@@ -43,6 +43,8 @@
43
43
  ```
44
44
 
45
45
 
46
+
47
+ ###私の問題を含んだ回答
46
48
 
47
49
  ```C++
48
50
 

10

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

2020/06/21 03:01

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -12,9 +12,11 @@
12
12
 
13
13
  ```
14
14
 
15
- ```C++
16
15
 
17
16
 
17
+ 定義
18
+
19
+ ```C++
18
20
 
19
21
  /**
20
22
 
@@ -37,6 +39,12 @@
37
39
  * };
38
40
 
39
41
  */
42
+
43
+ ```
44
+
45
+
46
+
47
+ ```C++
40
48
 
41
49
  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
42
50
 

9

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

2020/06/21 03:00

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -108,7 +108,7 @@
108
108
 
109
109
 
110
110
 
111
- ListNode *result;
111
+ ListNode *nodePtr;
112
112
 
113
113
  if(l1==NULL){
114
114
 
@@ -124,21 +124,21 @@
124
124
 
125
125
  if(l1->val<=l2->val){
126
126
 
127
- result=l1;
127
+ nodePtr=l1;
128
128
 
129
- result->next=mergeTwoLists(l1->next,l2);
129
+ nodePtr->next=mergeTwoLists(l1->next,l2);
130
130
 
131
131
  } else{
132
132
 
133
- result=l2;
133
+ nodePtr=l2;
134
134
 
135
- result->next=mergeTwoLists(l1,l2->next);
135
+ nodePtr->next=mergeTwoLists(l1,l2->next);
136
136
 
137
137
  }
138
138
 
139
139
 
140
140
 
141
- return result;
141
+ return nodePtr;
142
142
 
143
143
  }
144
144
 

8

模範解答の追加

2020/06/21 02:59

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -98,6 +98,50 @@
98
98
 
99
99
  ```
100
100
 
101
+ ###下記の模範解答も参考したのですが、私のコードとの違いがわかりません。
101
102
 
103
+ 模範回答
102
104
 
105
+ ```C++
106
+
107
+ ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
108
+
109
+
110
+
111
+ ListNode *result;
112
+
113
+ if(l1==NULL){
114
+
103
- //
115
+ return l2;
116
+
117
+ } else if(l2==NULL){
118
+
119
+ return l1;
120
+
121
+ }
122
+
123
+
124
+
125
+ if(l1->val<=l2->val){
126
+
127
+ result=l1;
128
+
129
+ result->next=mergeTwoLists(l1->next,l2);
130
+
131
+ } else{
132
+
133
+ result=l2;
134
+
135
+ result->next=mergeTwoLists(l1,l2->next);
136
+
137
+ }
138
+
139
+
140
+
141
+ return result;
142
+
143
+ }
144
+
145
+ };
146
+
147
+ ```

7

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

2020/06/21 02:57

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -1,16 +1,20 @@
1
+ このようなエラーが出ます。
2
+
3
+ ```
4
+
5
+ Line 30: Char 30: runtime error: member access within misaligned address 0x000000000001 for type 'ListNode', which requires 8 byte alignment (solution.cpp)
6
+
7
+ 0x000000000001: note: pointer points here
8
+
9
+ <memory cannot be printed>
10
+
1
- ### LeetCodeというサイトで、プログラミングの問題を説いているのですが、採点結果が、Time Limit Exceededとなります。
11
+ SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:39:30
12
+
13
+ ```
14
+
15
+ ```C++
2
16
 
3
17
 
4
-
5
- どうすれば解決すると思われますか？
6
-
7
-
8
-
9
- ### 該当のソースコード
10
-
11
-
12
-
13
- ```C++
14
18
 
15
19
  /**
16
20
 
@@ -34,15 +38,11 @@
34
38
 
35
39
  */
36
40
 
37
- class Solution {
38
-
39
- public:
40
-
41
- ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
41
+ ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
42
42
 
43
43
 
44
44
 
45
- //2つの並べ替えられたリンクリストをマージし、新しい並べ替えられたリストとして返します。 新しいリストは、最初の2つのリストのノードをつなぎ合わせて作成する必要があります。
45
+ //2つの並べ替えられたリンクリストを、新しい並べ替えられたリストとして返します。
46
46
 
47
47
  ListNode *nodePtr;
48
48
 
@@ -68,21 +68,23 @@
68
68
 
69
69
  //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
70
70
 
71
- if(l1->val >= l2->val){
71
+ if(l1->val <= l2->val){
72
+
73
+ //l1の値の方が小さいので、nodePtrはl1に連結させる
74
+
75
+ nodePtr->next=l1;
76
+
77
+ //リスト1を次の要素に進める
78
+
79
+ l1=l1->next;
80
+
81
+
82
+
83
+ }else{
72
84
 
73
85
  nodePtr->next=l2;
74
86
 
75
- //リスト２を次の要素に進める
76
-
77
- l2=l2->next;
87
+ l2=l2->next;
78
-
79
-
80
-
81
- }else if(l1->val <= l2->val){
82
-
83
- nodePtr->next=l1;
84
-
85
- l1=l1->next;
86
88
 
87
89
  }
88
90
 
@@ -90,12 +92,12 @@
90
92
 
91
93
  }
92
94
 
93
-
94
-
95
95
  return nodePtr;
96
96
 
97
97
  }
98
98
 
99
- };
99
+ ```
100
100
 
101
+
102
+
101
- ```
103
+ //

6

質問の修正

2020/06/21 02:53

投稿

edoooooo
edoooooo

スコア476

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

5

コードを改善しました。

2020/06/21 02:47

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -44,11 +44,7 @@
44
44
 
45
45
  //2つの並べ替えられたリンクリストをマージし、新しい並べ替えられたリストとして返します。 新しいリストは、最初の2つのリストのノードをつなぎ合わせて作成する必要があります。
46
46
 
47
- ListNode *nodePtr=new ListNode;
47
+ ListNode *nodePtr;
48
-
49
- int num1 , num2;
50
-
51
- bool again=true;
52
48
 
53
49
 
54
50
 

4

コードを改善しました。

2020/06/21 02:46

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -42,7 +42,9 @@
42
42
 
43
43
 
44
44
 
45
+ //2つの並べ替えられたリンクリストをマージし、新しい並べ替えられたリストとして返します。 新しいリストは、最初の2つのリストのノードをつなぎ合わせて作成する必要があります。
46
+
45
- ListNode *nodePtr;
47
+ ListNode *nodePtr=new ListNode;
46
48
 
47
49
  int num1 , num2;
48
50
 
@@ -54,69 +56,37 @@
54
56
 
55
57
  {
56
58
 
57
- if(l1!=NULL){
59
+ if(l1==NULL){
58
60
 
59
- num1=l1->val;
61
+ nodePtr->next=l2;
60
-
61
- }
62
62
 
63
63
 
64
64
 
65
- if(l2!=NULL){
65
+ }else if(l2==NULL){
66
66
 
67
- num2=l2->val;
67
+ nodePtr->next=l1;
68
-
69
- }
70
68
 
71
69
 
72
70
 
73
- //１と２の連結したものをリスト３にいれる
74
-
75
- //1つめの要素
76
-
77
- if(nodePtr==NULL){
78
-
79
-
80
-
81
- if(num1>=num2){
82
-
83
- nodePtr=new ListNode(num2);
84
-
85
- }else{
86
-
87
- nodePtr=new ListNode(num1);
88
-
89
- }
90
-
91
- //１つめ以降のリスト
92
-
93
71
  }else{
94
72
 
95
- //次の要素に進む
73
+ //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
96
74
 
97
- nodePtr=nodePtr->next;
75
+ if(l1->val >= l2->val){
98
76
 
99
-
77
+ nodePtr->next=l2;
100
78
 
101
- if(nodePtr!=NULL){
79
+ //リスト２を次の要素に進める
102
80
 
103
- //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
81
+ l2=l2->next;
104
82
 
105
- if(num1>=num2 || l1==NULL){ //←修正
83
+
106
84
 
107
- nodePtr->val=num2;
85
+ }else if(l1->val <= l2->val){
108
86
 
109
- //リスト２を次の要素に進める
87
+ nodePtr->next=l1;
110
88
 
111
- l2=l2->next;
112
-
113
- }else if(num2<num1 || l2==NULL){ //←修正
114
-
115
- nodePtr->val=num1;
116
-
117
- l1=l1->next;
89
+ l1=l1->next;
118
-
119
- }
120
90
 
121
91
  }
122
92
 

3

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

2020/06/21 02:40

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -1,10 +1,8 @@
1
1
  ### LeetCodeというサイトで、プログラミングの問題を説いているのですが、採点結果が、Time Limit Exceededとなります。
2
2
 
3
-
4
-
5
- 新しいリストは、最初の2つのリストのノードをつなぎ合わせて作成する必要があります。
6
3
 
7
4
 
5
+ どうすれば解決すると思われますか？
8
6
 
9
7
 
10
8
 
@@ -104,7 +102,7 @@
104
102
 
105
103
  //リスト１の要素よりもリスト２の要素が小さい場合は、リスト２の要素を先にリスト３に代入
106
104
 
107
- if(num1>=num2){
105
+ if(num1>=num2 || l1==NULL){ //←修正
108
106
 
109
107
  nodePtr->val=num2;
110
108
 
@@ -112,7 +110,7 @@
112
110
 
113
111
  l2=l2->next;
114
112
 
115
- }else{
113
+ }else if(num2<num1 || l2==NULL){ //←修正
116
114
 
117
115
  nodePtr->val=num1;
118
116
 

2

コードを少し変更

2020/06/21 02:17

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -52,7 +52,7 @@
52
52
 
53
53
 
54
54
 
55
- while(l2!=NULL && l1!=NULL)
55
+ while(l2!=NULL || l1!=NULL)
56
56
 
57
57
  {
58
58
 

1

問題の変更

2020/06/20 19:57

投稿

edoooooo
edoooooo

スコア476

test CHANGED
File without changes
test CHANGED
@@ -1,26 +1,8 @@
1
- ### 2つの並べ替えられたリンクリストをマージし、新しい並べ替えられたリストとして返したい。
1
+ ### LeetCodeというサイトで、プログラミングの問題を説いているのですが、採点結果が、Time Limit Exceededとなります。
2
2
 
3
3
 
4
4
 
5
5
  新しいリストは、最初の2つのリストのノードをつなぎ合わせて作成する必要があります。
6
-
7
- そこでこのようなエラーが出ます。
8
-
9
-
10
-
11
- ### エラー
12
-
13
- ```
14
-
15
- Line 77: Char 22: runtime error: member access within misaligned address 0xf3f3f3f8f1f1f1f1 for type 'const ListNode', which requires 8 byte alignment (_Serializer_.cpp)
16
-
17
- 0xf3f3f3f8f1f1f1f1: note: pointer points here
18
-
19
- <memory cannot be printed>
20
-
21
- SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior _Serializer_.cpp:86:22
22
-
23
- ```
24
6
 
25
7
 
26
8
 
@@ -70,7 +52,7 @@
70
52
 
71
53
 
72
54
 
73
- while(l2==NULL && l1==NULL)
55
+ while(l2!=NULL && l1!=NULL)
74
56
 
75
57
  {
76
58