これは、Microsoft の筆記試験で尋ねられたプログラミングの質問の 1 つです。私が考えた質問と回答をここに示します。私の回答は包括的に見えますが (少なくとも私には)、行数を減らすことができると思います。これは C で出題され、私は Java の人間ですが、なんとかコーディングできました (私の回答には Java のような構文が多すぎる可能性があります)
さて、質問です。
すでにソートされている 2 つのリストがある場合、それらを結合して、新しい追加ノードのない新しいリストを返す必要があります。返されるリストもソートされている必要があります。
メソッドシグネチャは、
Node* MergeLists(Node* list1, Node* list2);
struct Node{
int data;
Node *next;
}
私が思いついた解決策は次のとおりです。
Node* MergeLists(Node* list1, Node* list2){
Node* mergedList;
if(list1 == null && list2 ==null){//if both are null, return null
return null;
}
if(list1 == null){//if list1 is null, simply return list2
return list2;
}
if(list2 == null){//if list2 is null, simply return list1
return list1;
}
if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
mergedList = list1;
}else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
mergedList = list2;
}
while(list1!=null && list2!=null){
if(list1.data < list2.data){
mergedList->next = list1;
list1 = list1->next;
}else{
mergedList->next = list2;
list2 = list2->next;
}
}
if(list1 == null){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
mergedList->next = list2;
}else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
mergedList->next = list1;
}
return mergedList;
}
これは強化できると確信しています。重複して追加した行を見つけるのを手伝ってください。構文エラーやロジックについて遠慮なく批判してください。
ありがとう！
ベストアンサー1
最も目立つバグはループにあります。mergedList->next を上書きし続けるため、以前に追加されたノードが失われます。つまり、入力に関係なく、返されるリストには 2 つ以上のノードが含まれることはありません...
C をやったのは久しぶりですが、次のようにやります。
Node* merge(Node* list1, Node* list2) {
Node* merged = null;
Node** tail = &merged;
while (list1 && list2) {
if (list1->data < list2->data) {
*tail = list1;
list1 = list1->next;
} else {
*tail = list2;
list2 = list2->next;
}
tail = &((*tail)->next);
}
*tail = list1 ? list1 : list2;
return merged;
}