ヘルプ

Question

は、私は2つのソートされたリンクリストマージするには、次のコードを持っている：

struct node* merge(struct node* a, struct node* b) 
{ 
     struct node dummy;  

     struct node* tail = &dummy; 

     dummy.next = NULL; 
     while(1) 
     { 
       if(a == NULL) 
       { 
         tail->next = b; 
         break; 
       } 
       else if (b == NULL) 
       { 
         tail->next = a; 
         break; 
       } 
       if (a->data <= b->data) 
       { 
         MoveNode(&(tail->next), &a); 
       } 
       else 
       { 
         MoveNode(&(tail->next), &b); 
       } 
       tail = tail->next; 
     } 
     return(dummy.next); 
} 

void MoveNode(struct node** destRef, struct node** sourceRef) 
{ 
     struct node* newNode = *sourceRef; 

     *sourceRef = newNode->next; 

     newNode->next = *destRef; 

     *destRef = newNode; 
} 

をそして、それがうまく働きました。私は、再帰的なメソッドにそれをしようとしていた、これは私が得たものである：

struct node* Merge(struct node* a, struct node* b) 
{ 
     struct node* result; 

     if (a == NULL) 
       return(b); 
     else if (b==NULL) 
       return(a); 

     if (a->data <= b->data) 
     {     
       result = Merge(a->next, b); 
     } 
     else 
     {     
       result = Merge(a, b->next); 
     } 
     return(result); 
} 

しかし、それは結果に欠けているノードの多くを持っています。なにが問題ですか？

Answer 1

あなたの基本条件は正しいです。しかし、あなたの再帰条件に問題があります。

あなたがresultにノードaまたはノードbをコピーしていないsのデータa「bとのデータ」を比較します。

試してみてください。

struct node* result; 

if (a == NULL)   
     return(b);      
else if (b==NULL)        
     return(a);            

if (a->data <= b->data)             
{   
     // make result point to node a.           
     result = a;  
     // recursively merge the remaining nodes in list a & entire list b 
     // and append the resultant list to result. 
     result->next = Merge(a->next, b); 
} 
else          
{     
     result = b; 
     result->next = Merge(a, b->next);    
} 
return(result);