Fusion de deux listes triées liées

il s'agit d'une des questions de programmation posées lors du test écrit de Microsoft. Je fais la question et la réponse que j'ai trouvé. Chose est de ma réponse, bien que les regards globale (au moins pour moi), j'ai l'impression que le nombre de lignes peut être réduite. Il a été demandé en C et je suis une personne Java, mais j'ai réussi à le coder (ma réponse peut contenir trop de Java comme syntaxes)

Ok, voici la question.

vous avez deux listes qui sont déjà triés, vous devez les fusionner et retourne une nouvelle liste sans nouvelles supplémentaires nœud. La liste retournée doit être triées.

la signature de La méthode est,

Node* MergeLists(Node* list1, Node* list2);

struct Node{
    int data;
    Node *next;
}

la solution que j'ai trouvée est la suivante,

Node* MergeLists(Node* list1, Node* list2){
    Node* mergedList;
    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;
    }
    if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
        mergedList = list1;
    }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
        mergedList = list2;
    }
    while(list1!=null && list2!=null){
        if(list1.data < list2.data){
            mergedList->next = list1;
            list1 = list1->next;
        }else{
            mergedList->next = list2;
            list2 = list2->next;
        }
    }
    if(list1 == null){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
        mergedList->next = list2;
    }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
        mergedList->next = list1;
    }
    return mergedList;
}

je suis très confiant cela peut être amélioré. S'il vous plaît aidez-moi à trouver quelles lignes sont redondantes j'ai ajouté. N'hésitez pas à critiquer mes les erreurs de syntaxe et de la logique.

Merci!

23
demandé sur bragboy 2010-02-27 21:00:44
la source

14 ответов

votre code est surchargé de if - s inséré pour traiter les cas" spéciaux", ce qui le gonfle beaucoup et le rend difficile à lire. Cela se produit généralement lorsque vous décidez de gérer des cas particuliers "code" au lieu de trouver un moyen de gérer les "données". Une affirmation attribuée à David Wheeler dit "Tous les problèmes en informatique peuvent être résolus par un autre niveau d'indirectement". Ce "niveau supplémentaire d'indirectement" fonctionne généralement très bien avec les listes, en aidant à réduire l'encombrement créé par ces if .

pour illustrer ce qui précède, voici à quoi ressemblerait mon code

#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (0)

Node* MergeLists(Node* list1, Node* list2) 
{
  Node *list = NULL, **pnext = &list;

  if (list2 == NULL)
    return list1;

  while (list1 != NULL)
  {
    if (list1->data > list2->data)
      SWAP_PTRS(list1, list2);

    *pnext = list1;
    pnext = &list1->next;
    list1 = *pnext;
  }

  *pnext = list2;
  return list;
}

Certains pourraient faire valoir que l'utilisation d'un niveau supplémentaire d'indirection dans pnext pointeur rend le code plus difficile à lire. Je suis d'accord que pour un débutant l'approche pourrait poser quelques difficultés, mais pour un programmeur expérimenté ce devrait être facilement digestible comme un idiome.

13
répondu AnT 2013-01-16 10:44:20
la source

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;
}
18
répondu meriton 2010-02-27 21:22:19
la source

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;
}
9
répondu DigitalRoss 2010-02-27 22:12:41
la source

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.

5
répondu polygenelubricants 2010-02-27 22:10:27
la source

Divide et Impera

(c'est à dire MergeSort )

4
répondu Luca 2010-10-04 21:58:48
la source

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.

2
répondu piccolbo 2010-10-16 02:28:15
la source

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;
}
2
répondu herohuyongtao 2013-12-17 17:41:52
la source
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.

0
répondu Naveen 2012-02-14 13:42:06
la source

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;
}
0
répondu Ronen 2013-03-13 12:29:49
la source
#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;
}
0
répondu Abhishek Jadhav 2016-02-11 18:21:23
la source

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.

0
répondu Brijesh Valera 2016-02-19 09:45:53
la source

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;
}
0
répondu Abhishek Kshirsagar 2016-09-16 07:20:19
la source

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);
0
répondu Rupesh Kumar 2017-01-01 22:01:45
la source
//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);

}
-1
répondu learner 2018-01-01 14:18:45
la source

Autres questions sur