Я пытаюсь объединить два отсортированных связанных списка

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; 

Answer 2

я могу предложить следующее решение

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

typedef struct node 
{ 
    int data; 
    struct node *next; 
} Node; 

int add(Node **head, int value) 
{ 
    Node *tmp = malloc(sizeof(Node)); 
    int success = tmp != NULL; 

    if (success) 
    { 
     tmp->data = value; 

     if (*head == NULL || value < (*head)->data) 
     { 
      tmp->next = *head; 
      *head = tmp; 
     } 
     else 
     { 
      while ((*head)->next && !(value < (*head)->next->data)) head = &(*head)->next; 

      tmp->next = (*head)->next; 
      (*head)->next = tmp; 
     } 
    } 

    return success; 
} 

void display(Node *head) 
{ 
    for (; head != NULL; head = head->next) printf(" %d", head->data); 
    printf("\n"); 
} 

Node * MergeLists(Node *headA, Node *headB) 
{ 
    Node *headC = NULL; 
    Node **tailC = &headC; 

    while (headA && headB) 
    { 
     *tailC = malloc(sizeof(Node)); 

     if (*tailC != NULL) 
     { 
      if (headB->data < headA->data) 
      { 
       (*tailC)->data = headB->data; 
       headB = headB->next; 
      } 
      else 
      { 
       (*tailC)->data = headA->data; 
       headA = headA->next; 
      } 

      tailC = &(*tailC)->next; 
     }   
    } 

    while (headA != NULL) 
    { 
     *tailC = malloc(sizeof(Node)); 

     if (*tailC != NULL) 
     { 
      (*tailC)->data = headA->data; 
      headA= headA->next; 
      tailC = &(*tailC)->next; 
     } 
    } 

    while (headB != NULL) 
    { 
     *tailC = malloc(sizeof(Node)); 

     if (*tailC != NULL) 
     { 
      (*tailC)->data = headB->data; 
      headB= headB->next; 
      tailC = &(*tailC)->next; 
     } 
    } 

    return headC; 
} 

int main(void) 
{ 
    const int N = 10; 

    Node *headA = NULL; 
    Node *headB = NULL; 

    srand((unsigned int)time(NULL)); 

    for (int i = 0; i < N; i++) add(&headA, rand() % N); 
    for (int i = 0; i < N; i++) add(&headB, rand() % N); 

    printf("List A:"); display(headA); 
    printf("List B:"); display(headB); 

    Node *headC = MergeLists(headA, headB); 
    printf("List C:"); display(headC); 

    return 0; 
} 

Выход программы может выглядеть

List A: 1 3 3 3 3 4 7 8 9 9 
List B: 0 0 2 3 4 4 4 5 6 9 
List C: 0 0 1 2 3 3 3 3 3 4 4 4 4 5 6 7 8 9 9 9