Fusionando dos listas enlazadas ordenadas

Esta es una de las preguntas de progtwigción realizadas durante la prueba escrita de Microsoft. Estoy dando la pregunta y la respuesta que se me ocurrió. La cosa es mi respuesta, aunque parece completa (al menos para mí), creo que se puede reducir el número de líneas. Se me preguntó en C y soy una persona de Java, pero logré codificarlo (mi respuesta puede contener demasiadas syntax como Java)

Ok, aquí está la pregunta.

Tiene dos listas que ya están ordenadas, debe fusionarlas y devolver una nueva lista sin ningún nodo adicional. La lista devuelta debe ser ordenada también.

La firma del método es,

Node* MergeLists(Node* list1, Node* list2); struct Node{ int data; Node *next; } 

La siguiente es la solución que se me ocurrió,

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

Estoy muy seguro de que esto se puede mejorar. Por favor, ayúdame a encontrar las líneas que he agregado de forma redundante. Por favor, siéntase libre de criticar mis errores de syntax y lógica.

¡Gracias!

Su código está sobrecargado con -s insertado para manejar casos “especiales”, lo cual lo hincha mucho y hace que sea difícil de leer. Esto generalmente ocurre cuando decides manejar casos especiales “por código” en lugar de encontrar una manera de manejarlos “por datos”. Una statement atribuida a David Wheeler dice: “Todos los problemas en la informática se pueden resolver con otro nivel de indirección”. Ese “nivel adicional de indirección” generalmente funciona muy bien con las listas, lo que ayuda a reducir significativamente el desorden creado por aquellos if s.

Para ilustrar lo anterior, esto es lo que mi código se vería

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

Algunos podrían argumentar que el uso de un nivel extra de indirección en el puntero pnext hace que el código sea más difícil de leer. Estoy de acuerdo en que para un novato, el enfoque podría plantear algunas dificultades, pero para un progtwigdor experimentado esto debería ser fácilmente asimilable como un modismo.

El error más evidente está en tu ciclo, sigues sobrescribiendo mergedList-> next, perdiendo el nodo agregado previamente. Es decir, su lista devuelta nunca contendrá más de dos nodos, independientemente de la entrada …

Ha pasado un tiempo desde que hice C, pero lo haría de la siguiente manera:

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

Mi opinión, con un caso de prueba

Hasta ahora, todas las respuestas han sido interesantes y bien hechas. Es posible que este sea más como lo que un entrevistador quisiera ver, con DRY / DIE y TDD. 🙂

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

No se vuelve más elegante que esto:

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

Suponiendo que comprenda la recursión, esto es lo más claro posible.


Debo señalar que esto es bueno para una respuesta de entrevista solamente (donde presumiblemente demostrar claridad de pensamiento tiene más impacto que simplemente mostrar que sabes cómo escribir progtwigs). En la práctica, no querrá fusionarse de esta manera, ya que usa la profundidad de la stack O(n) , lo que probablemente causaría un desbordamiento de la stack. Además, no es una recursividad de cola, por lo que no es optimizable para el comstackdor.

Divide y vencerás

(es decir, MergeSort )

Así que fusionando Polygen con AndreyT obtenemos:

 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)} 

No puedo reclamar el mérito de este, pero es el más conciso y muestra la simetría entre los dos argumentos, no introduce ninguna función auxiliar oscura. No estoy seguro de que un comstackdor de optimización vea una repetición de cola aquí, pero lo hago. La sangría es un toque final.

Use recursión. El código es el siguiente:

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

Hola chicos ! Me estaba preparando para una entrevista este mes y mientras estaba trabajando en este problema, esta es la solución que se me ocurrió. Comparé mi solución con muchas soluciones que publicó aquí y encuentro que mi progtwig es extremadamente extenso. Aunque considero que esto es más fácil de comprender e implementar, ¿existe una mejor solución en Java para el código existente? Estoy buscando una mejor solución de complejidad de tiempo. Cualquier ayuda / dirección / sugerencia es apreciada.

PD: No pude encontrar una solución Java para los progtwigs enumerados anteriormente en C que usa punteros.

Esta es mi opinión. A diferencia de otras soluciones, identifica y omite nodos consecutivos en una lista que son más pequeños o iguales al nodo principal de la otra lista. El encabezado de la otra lista se adjunta al final de dicha secuencia y el proceso se repite después de cambiar de roles. Este enfoque minimiza la cantidad de asignaciones a Node.next al tiempo que limita la prueba NULL a la comprobación individual en cada iteración.

 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 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;idata=value; newNode->next=NULL; if(i!=0) { ptr->next=newNode; ptr=ptr->next; } if(i==0) { head1=newNode; ptr=newNode; } } for(i=0;idata=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; } 

He creado la función de recursión para él. Aquí está mi solución:

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

Guarde el puntero de retorno en la nueva variable de puntero (en la función principal /) y atraviese la lista vinculada en un puntero nuevo para imprimir datos; se obtendrá una lista enlazada fusionada ordenada.

Puedes usar recursión:

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

Puede usar Java 8, Stream API para combinar, obtener Distinct y ordenar. A continuación se muestra el código de ejemplo para ordenar y fusionar dos listas con elementos enteros

 List list1= Arrays.asList(2,3,5,8); List list2 = Arrays.asList(3,6,8); List finalList = new ArrayList<>(); finalList.addAll(list1); finalList.addAll(list2); List 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 #include #include 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->datadata){ 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); }