帮助与递归函数

Question

我有下面的代码合并两个排序链表：

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

您的基本情况是正确的。但是递归条件存在问题。

当你比较a的数据与b的数据你是不是复制节点a或节点b到result。

尝试：

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);