c - 我正在尝试合并两个排序的链表

Question

在这里，我试图合并两个排序的链接列表，但我的代码根本不起作用，所以有人能告诉我我做错了什么吗？这是执行合并两个排序链表的函数

   Node* MergeLists(Node *headA, Node* headB)

     {

     Node *temp,*ptr,*par;
      ptr=headA;
    par=headB;
    int c=0,s=0,t;
    while(ptr!=NULL)
        {
        ptr=ptr->next;
        c++;
    }
    while(par!=NULL)
        {
        par=par->next;
        s++;
    }
    t=c+s;
    //cout<<t<<"\n";
    temp=(Node*)malloc(t*sizeof(Node));
    if(headA->data <= headB->data)
        {
        temp=headA;
        ptr=headA->next;
        par=headB;
    }
    else
        {
        temp=headB;
        par=headB->next;
        ptr=headA;
    }
    while(ptr!=NULL && par!=NULL)
        {
        if(ptr->data>=par->data)
            {

            temp->next=par;
            par=par->next;
        }
        else
            {

            temp->next=ptr;
        ptr=ptr->next;
        }
        temp=temp->next;
    }
    while(ptr!=NULL)
        {
        temp->next=ptr;
        ptr=ptr->next;
        temp=temp->next;
    }
    while(par!=NULL)
        {
        temp->next=par;
        par=par->next;
        temp=temp->next;
    }
    temp->next=NULL;
     while(temp!=NULL)
        {

       cout<<temp->data<<" ";
        temp=temp->next;
    }
    return temp;
}

Answer 1

链表是一种基于指针的动态数据结构。

您犯的主要错误是分配巨大的连续堆内存，就好像您的新链接列表是数组。

所以，在那之后的解决方案是完全错误的。

下面的代码应该按排序顺序合并两个已排序的链表，并返回指向新链表的指针。

Node* tempA, *tempB, *newTemp, *newHead;
tempA = headA;
tempB = headB;

newTemp = (Node*) malloc( sizeof(Node));
newHead = newTemp;

while( tempA && tempB)
{
    if( tempA->data <= tempB->data){
        newTemp->data = tempA->data;
        tempA = tempA->next;
    }
    else{
        newTemp->data = tempB->data;
        tempB = tempB->next;
    }

    newTemp->next = (Node*) malloc( sizeof(Node));
    newTemp = newTemp->next;
}

while( tempA)
{
    newTemp->data = tempA->data;
    tempA = tempA->next;

    newTemp->next = (Node*) malloc( sizeof(Node));
    newTemp = newTemp->next;
}

while( tempB)
{
    newTemp->data = tempB->data;
    tempA = tempB->next;

    newTemp->next = (Node*) malloc( sizeof(Node));
    newTemp = newTemp->next;
}

free(newTemp); //last one is useless.

return newHead;