Ich versuche die beiden sortierten verknüpften Listen zusammenzuführen

Question

Hier versuche ich zwei sortierte verknüpfte Listen zusammenzuführen, aber mein Code funktioniert überhaupt nicht, kann mir also jemand sagen, was ich falsch mache? Dies ist die Funktion, die die Aufgabe der Zusammenführung zweier sortierter verkettete Listen funktioniert

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

Eine verkettete Liste ist ein Zeiger auf Basis dynamische Datenstruktur.

Der Hauptfehler Sie ein Array tat zuteilt ein großer aufeinander folgenden Heap-Speicher, als ob Ihre neue verknüpfte Liste ist.

Also ist die Lösung nach diesem Punkt völlig falsch.

Der folgende Code sollte zwei sortierte verknüpfte Listen in sortierter Reihenfolge zusammenführen und einen Zeiger auf die neue verknüpfte Liste zurückgeben.

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

kann ich vorschlagen, die folgende Lösung

#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; 
} 

Das Programm Ausgabe wie

aussehen könnte

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