c - 递归函数帮助

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