Fusion de deux listes triées liées

le bogue le plus flagrant est dans votre boucle, vous continuez à écraser mergedList->next, en perdant le noeud précédemment ajouté. C'est-à-dire que votre liste retournée ne contiendra jamais plus de deux noeuds, indépendamment de l'entrée ...

Cela fait longtemps que je N'ai pas fait C, mais je le ferais comme suit:

Node* merge(Node* list1, Node* list2) {
    Node* merged = null;
    Node** tail = &merged;

    while (list1 && list2) {
        if (list1->data < list2->data) {
            *tail = list1;
            list1 = list1->next;
        } else {
            *tail = list2;
            list2 = list2->next;
        }
        tail = &((*tail)->next);
    }
    *tail = list1 ? list1 : list2;
    return merged;
}

de Mon point de vue, à un cas de test

jusqu'à présent, toutes les réponses ont été intéressant et bien fait. Il est possible que celui-ci ressemble davantage à ce qu'un intervieweur aimerait voir, avec DRY/DIE, et TDD. :- )

#include <stdio.h>

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

Node l1[] = {
  { 1, &l1[1] },
  { 3, &l1[2] },
  { 5, &l1[3] },
  { 7, &l1[4] },
  { 9, &l1[5] },
  {11, 0 },
};

Node l2[] = {
  { 2, &l2[1] },
  { 4, &l2[2] },
  { 6, 0 },
};

Node* MergeLists(Node* list1, Node* list2) {
  Node *t, **xt;
  for(xt = &t; list1 || list2;) {
    Node **z = list1 == NULL ? &list2 :
               list2 == NULL ? &list1 :
               list1->data < list2->data ? &list1 : &list2;
    *xt = *z;
     xt = &(*z)->next;
    *z  = *xt;
  }
  *xt = NULL;
  return t;
}

int main(void) {
  for(Node *t = MergeLists(l1, l2); t; t = t->next) 
    printf("%d\n", t->data);
  return 0;
}

il n'y a pas plus élégant que celui-ci:

Node* merge2(Node* n1, Node* n2) {
    n1->next = merge(n1->next, n2);
    return n1;
}

Node* merge(Node* n1, Node* n2) {
    return (n1 == null) ? n2 :
           (n2 == null) ? n1 :
           (n1->data < n2->data) ?
               merge2(n1, n2) :
               merge2(n2, n1);
}

en supposant que vous comprenez la récursion, c'est aussi clair que possible.

je dois souligner que c'est bon pour une réponse d'entrevue seulement (où probablement démontrer la clarté de la pensée a plus d'impact que simplement montrer que vous savez écrire des programmes). En pratique, vous ne voudriez pas fusionner de cette façon, puisqu'il utilise la pile O(n) la profondeur, ce qui causerait probablement un débordement de la pile. De plus, ce n'est pas une récursion de queue, donc ce n'est pas un compilateur-optimisable.

Divide et Impera

(c'est à dire MergeSort )

ainsi fusion de polygen avec AndreyT nous obtenons:

Node* merge(Node* n1, Node* n2) {
    return (n1 == null) ? n2 :
           (n2 == null) ? n1 :
             (n1->data < n2->data) ? 
               (n1->next = merge(n1->next, n2), n1) : 
               (n2->next = merge(n2->next, n1), n2)}

Je ne peux pas revendiquer le crédit pour celui-ci, mais il est le plus concis et montre la symétrie entre les deux arguments, n'introduit pas de fonctions d'aide obscures. Je ne suis pas sûr qu'un compilateur optimisant verra une recursion de la queue ici, mais je le fais. L'indentation est une touche finale.

utiliser la récursion. Le code est le suivant:

ListNode* mergeTwoSortedLists(ListNode* pHead1, ListNode* pHead2)
{
    if(pHead1 == NULL)
        return pHead2;
    else if(pHead2 == NULL)
        return pHead1;

    ListNode* pMergedHead = NULL;

    if(pHead1->m_nValue < pHead2->m_nValue)
    {
        pMergedHead = pHead1;
        pMergedHead->m_pNext = mergeTwoSortedLists(pHead1->m_pNext, pHead2);
    }
    else
    {
        pMergedHead = pHead2;
        pMergedHead->m_pNext = mergeTwoSortedLists(pHead1, pHead2->m_pNext);
    }

    return pMergedHead;
}

public void Merge(LinkList list1, LinkList list2) {
        if (list1.head == null && list2.head == null) {
            System.out.println("Empty list"); //Check if lists are empty
        }
        if (list1.head == null) { //If list1 is empty print list2
            list2.printList();
        }
        if (list2.head == null) { //If list2 is empty print list1
            list1.printList(); 
        }
        LinkList list3 = new LinkList(); //create a new LinkList object for merging
        Node a = list1.head; //Beginning of list1
        Node b = list2.head; //Beginning of list2
        while (a != null && b != null) { //Until list ends
            if (a.value <= b.value) { //Compare values of list1 against list2
                list3.insert(a.value); //Insert values to new list
                a = a.next;
            } else if (a.value >= b.value) {
                list3.insert(b.value);
                b = b.next;
            }  else if (a.value == b.value){ //Insert only unique values and discard repeated values
            list3.insert(a.value);
            a = a.next;
            b = b.next;
        }
        }
        if (a == null) {
            while (b != null) {
                list3.insert(b.value); //If list1 becomes empty, attach rest of the list2 to list3
                b = b.next;
            }
        }
        if (b == null) {
            while (a != null) {
                list3.insert(a.value);
                a = a.next;
            }
        }
        list3.printList(); //print merged list
    }
}

Salut Les gars ! Je me préparais pour une interview ce mois-ci et alors que je travaillais sur ce problème, c'est la solution que j'ai trouvé. J'ai comparé ma solution avec de nombreuses solutions que vous avez publiées ici et je trouve mon programme extrêmement long. Bien que je trouve cela plus facile à comprendre et à mettre en œuvre, y a-t-il une meilleure solution en Java pour le code existant. Je cherche une meilleure solution de complexité temporelle. Toute aide / direction / conseil est apprécié.

PS: I a été incapable de trouver une solution Java pour les programmes énumérés ci-dessus dans C qui ont utilisé des pointeurs.

c'est mon avis. Contrairement à d'autres solutions, il identifie et saute sur les noeuds consécutifs sur une liste qui sont plus petits ou égaux au noeud de tête de l'autre liste. La tête de l'autre liste est jointe à la fin de la séquence, et le processus est répété après un échange de rôles. Cette approche minimise le nombre d'attributions au noeud.ensuite, en limitant le test nul à une seule vérification à chaque itération.

Node * merge(Node *list1, Node *list2)
{
    if (!list1) return list2;
    if (!list2) return list1;

    Node *tmp;

    // compare head nodes and swap lists to guarantee list1 has the smallest node
    if (list1->val > list2->val) {
        tmp = list2;
        list2 = list1;
        list1 = tmp;
    }

    Node *tail = list1;

    do {
        // Advance the tail pointer skipping over all the elements in the result
        // which have smaller or equal value than the first node on list2
        while (tail->next && (tail->next->val <= list2->val)) {
            tail = tail->next;
        }
        // concat list2 at tail of result and make the rest after tail list2 
        tmp = tail->next;
        tail->next = list2;
        tail = list2;
        list2 = tmp;
    } while (list2);

    return list1;
}

#include<stdio.h>

typedef struct NODE
{
    int data;
    struct NODE * next;
}NODE;

NODE * func(NODE*,NODE*);
int main()
{
    int i;
    int size;
    int value;
    NODE * head1,*head2,*newNode,*ptr,*final;
    printf("\nPlease enter the number of elements\n");
    scanf("%d",&size);

    for(i=0;i<size;i++)
    {
            printf("List 1\n");
            printf("Please enter the value number %d \n",i+1);
            scanf("%d",&value);
            newNode=(NODE*)malloc(sizeof(NODE));
            newNode->data=value;
            newNode->next=NULL;
            if(i!=0)
            {
                ptr->next=newNode;  
                ptr=ptr->next;
            }

            if(i==0)
            {
                head1=newNode;
                ptr=newNode;

            }
    }
    for(i=0;i<size;i++)
    {
            printf("\n\nList 2\n");
            printf("Please enter the value number %d \n",i+1);
            scanf("%d",&value);
            newNode=(NODE*)malloc(sizeof(NODE));
            newNode->data=value;
            newNode->next=NULL;
            if(i!=0)
            {
                ptr->next=newNode;  
                ptr=ptr->next;
            }

            if(i==0)
            {
                head2=newNode;
                ptr=newNode;

            }
    }

    final=func(head1,head2);
    printf("\n\n");
    while (final!=NULL)
    {
        printf("%d -->",final->data);
        final=final->next;
    }
    printf("NULL
    ");
    return 0;
}

NODE* func(NODE* list1, NODE* list2)
{

    NODE* mergedList,*mergeHead=NULL;
    if(list1 == NULL && list2 ==NULL){//if both are NULL, return NULL
        return NULL;
    }
    if(list1 == NULL){//if list1 is NULL, simply return list2
        return list2;
    }
    if(list2 == NULL){//if list2 is NULL, simply return list1
        return list1;
    }
    mergedList = (NODE*)malloc(sizeof(NODE));
    if(list1->data < list2->data){//initialize mergedList pointer to list1 if list1's data is lesser

        mergedList->data=list1->data;
        mergedList->next=NULL;
        list1 = list1->next;

    }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
        mergedList->data=list2->data;
        mergedList->next=NULL;
        list2 = list2->next;

    }
    mergeHead=mergedList;

    while(list1!=NULL && list2!=NULL){
        if(list1->data < list2->data){
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list1->data;
            mergedList->next=NULL;
            list1 = list1->next;
        }else{
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list2->data;
            mergedList->next=NULL;
            list2 = list2->next;
        }
    }
    if(list1 == NULL){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
       while(list2!=NULL)
       {
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list2->data;
            mergedList->next=NULL;
            list2 = list2->next;
       }

    }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list1->data;
            mergedList->next=NULL;
            list1 = list1->next;
    }
    return mergeHead;
}

j'ai créé une fonction de récursion pour elle. Voici ma solution:

Node* merge_recursion(Node* l1, Node* l2)
{
        if (!l1)
                return l2;
        if (!l2)
                return l1;

        if (l1->data < l2->data) {
                l1->next = merge_recursion(l1->next, l2);
                return l1;
        } else {
                l2->next = merge_recursion(l1, l2->next);
                return l2;
        }
}

stocke le pointeur de retour dans la nouvelle variable pointeur (dans la fonction main () / calling) et traverse la liste liée sur le nouveau pointeur pour imprimer des données, il en résultera une liste liée fusionnée triée.

vous pouvez utiliser recursion:

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

if(headA==NULL){
    return headB;
}else if(headB ==NULL){
    return headA;
}
Node* head = NULL;
if(headA->data <= headB->data){
    head= headA;
    head->next = MergeLists(headA->next,headB);
}else{
    head= headB;
    head->next = MergeLists(headA,headB->next);
}
 return head;
}

vous pouvez utiliser Java 8, stream API pour fusionner, obtenir Distinct et trier. Ci-dessous un exemple de code pour trier et fusionner deux listes avec des éléments entiers

List<Integer> list1= Arrays.asList(2,3,5,8);
List<Integer> list2 = Arrays.asList(3,6,8);

List<Integer> finalList = new ArrayList<>();
finalList.addAll(list1);
finalList.addAll(list2);

List<Integer>  mergeSortedList = 
  finalList.stream()
    .distinct()
    .sorted()
    .collect(Collectors.toList());
System.out.println(mergeSortedList);

//I have used recursions .
//Sorry for such a long code.
//:) it works,hope it helps.
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct node{
    int data;
    struct node *next ;
};
struct node *start1=NULL,*start2=NULL;
struct node*start=NULL;
struct node *create_ll1(struct node *start);
struct node *create_ll2(struct node *start);
void sorted_ll(struct node* node1,struct node* node2);

struct node *display(struct node *start);
void p(struct node*);
main(){
    start1=create_ll1(start1);
    start2=create_ll2(start2);
    //start1=display(start1);
    printf("\n");
    //start2=display(start2);
    sorted_ll(start1,start2);
    //start=display(start);


}
struct node *create_ll1(struct node *start1){
    struct node *ptr,*new_node;
    int num;
    printf("Enter -1 for ending \n");
    printf("Enter data for list 1: \n");
    scanf("%d",&num);
    while(num!=-1){
        new_node=(struct node *)malloc(sizeof(struct node));
        new_node->data=num;
        if(start1==NULL){
            new_node->next=NULL ;
            start1=new_node;
        }
        else{
            ptr=start1 ;
            while(ptr->next!=NULL)
            ptr=ptr->next;
            ptr->next=new_node;
            new_node->next=NULL ;
        }
        printf("Enter data: \n");
        scanf("%d",&num);
    }
    return start1;

}
struct node *create_ll2(struct node *start2){
    struct node *ptr,*new_node;
    int num;
    printf("Enter -1 for ending \n");
    printf("Enter data for list 2: \n");
    scanf("%d",&num);
    while(num!=-1){
        new_node=(struct node *)malloc(sizeof(struct node));
        new_node->data=num;
        if(start2==NULL){
            new_node->next=NULL ;
            start2=new_node;
        }
        else{
            ptr=start2 ;
            while(ptr->next!=NULL)
            ptr=ptr->next;
            ptr->next=new_node;
            new_node->next=NULL ;
        }
        printf("Enter data: \n");
        scanf("%d",&num);
    }
    return start2;

}

struct node *display(struct node *start){
    struct node *ptr;
    ptr=start;
    while(ptr->next!=NULL){
        printf("\t %d",ptr->data);
        ptr=ptr->next;
    }
        printf("\t %d",ptr->data);
        printf("\n");


    return start ;
}
void sorted_ll(struct node* node1,struct node* node2)
{
    if(!node1){
        p(node2);
        exit(0);
    }
    else if(!node2){
        p(node1);
        exit(0);
    }
    if(node1->data<node2->data){
        printf("%d\t",node1->data);
        sorted_ll(node1->next,node2);


    }
    else{
        printf("%d\t",node2->data);
        sorted_ll(node1,node2->next);
    }
}
void p(struct node* pme){
    while(pme->next!=NULL){
        printf("%d \t",pme->data);
        pme=pme->next;
    }
    printf("%d",pme->data);

}