Fusión de dos listas enlazadas ordenadas

8 minutos de lectura

avatar de usuario
fanfarrón

Esta es una de las preguntas de programación formuladas 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í), siento que la cantidad de líneas se puede reducir. Se preguntó en C y soy una persona de Java, pero logré codificarlo (mi respuesta puede contener demasiadas sintaxis similares a Java)

Bien, aquí está la pregunta.

Tiene dos listas que ya están ordenadas, debe fusionarlas y devolver una nueva lista sin nuevos nodos adicionales. La lista devuelta también debe ordenarse.

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

Estoy muy seguro de que esto se puede mejorar. Por favor, ayúdenme a encontrar qué líneas son redundantes que he agregado. Siéntase libre de criticar mis errores de sintaxis y lógica.

¡Gracias!

  • Parte de su código se puede acortar simplemente usando operadores trinarios al principio. IE reescriba las pruebas de parámetros usando mergedList = (list1 == null ? list2 : null) y guarde líneas de código, aunque ‘no’ operaciones.

    –Daniel Goldberg

    27 de febrero de 2010 a las 18:03

  • Bragboy, ¿te importaría cambiar tu título a una forma más descriptiva como “Fusión de dos listas ordenadas”? Su título actual (Necesito su consejo/consejos sobre este problema de codificación) es para lo que todos estamos aquí. 🙂 No identifica ni promueve su pregunta.

    – corredor de borde

    4 oct 2010 a las 18:04

avatar de usuario
merito

El error más evidente está en su ciclo, sigue sobrescribiendo mergedList-> next, perdiendo el nodo agregado anteriormente. 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;
}

  • ¡Hombre! ¡Eso es un GRAN AGUJERO!. Realmente no me di cuenta de eso.

    – fanfarrón

    27 de febrero de 2010 a las 18:12

avatar de usuario
Hormiga

Su código está sobrecargado con if-s insertado para manejar casos “especiales”, lo que lo infla mucho y dificulta su lectura. Esto suele suceder cuando decide manejar casos especiales “por código” en lugar de encontrar una manera de manejarlos “por datos”. Una declaración atribuida a David Wheeler dice: “Todos los problemas en 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 esos ifs.

Para ilustrar lo anterior, así es como se vería mi código

#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 adicional de indirección en pnext puntero en realidad hace que el código sea más difícil de leer. Estoy de acuerdo en que para un novato el enfoque puede presentar algunas dificultades, pero para un programador experimentado, esto debería ser fácilmente digerible como una expresión idiomática.

  • Gracias. Se considerará este tipo de enfoque para abordar problemas de esta naturaleza en el futuro. ¡Eso realmente ayudó!

    – fanfarrón

    27 de febrero de 2010 a las 18:28

  • ¿No sería este un intento de desreferenciar null Cuándo null se pasa por list2?

    – mérito

    27 de febrero de 2010 a las 18:29

  • @meriton: Sí, lo haría. Agregué un cheque extra 🙂 Gracias.

    – Ant

    27 de febrero de 2010 a las 18:30

  • +1 para obtener una explicación sobre la indirección y simplificar la condición while para verificar solo el puntero modificado.

    – mérito

    27 de febrero de 2010 a las 18:35

  • @polygenelubricants: Un error tipográfico. La intención era volver list1 (no list) Cuándo list2 es nulo. Reparado.

    – Ant

    27 de febrero de 2010 a las 18:39


Mi opinión, con un caso de prueba

Hasta ahora, todas las respuestas han sido interesantes y bien hechas. Es posible que este se parezca más a lo que le gustaría ver a un entrevistador, con DRY/DIE y 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;
}

  • Esa es una forma ingeniosa de construir una lista enlazada. Me encanta.

    – poligenolubricantes

    27 de febrero de 2010 a las 19:40

avatar de usuario
poligenelubricantes

No hay nada 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);
}

Asumiendo que entiendes la recursividad, esto es tan claro como parece.


Debo señalar que esto es bueno solo para una respuesta de entrevista (donde presumiblemente demostrar claridad de pensamiento tiene más impacto que simplemente demostrar que sabe cómo escribir programas). En la práctica, no querrá fusionarse de esta manera, ya que utiliza O(n) profundidad de la pila, lo que probablemente provocaría un desbordamiento de la pila. Además, no es una recursión de cola, por lo que no es optimizable por compilador.

avatar de usuario
Lucas

Divide y vencerás

(es decir combinarordenar)

  • Esta es exactamente la respuesta correcta, ¿por qué los votos negativos? @Luca: +1 de mí.

    – tzaman

    27 de febrero de 2010 a las 18:19


  • @tzaman: ¿Cómo diablos es esta una respuesta relacionada con esta pregunta?

    – fanfarrón

    27 de febrero de 2010 a las 18:33

  • @Bragaadeesh: ¿Tienes que ordenar? Me pregunto por qué no usar algoritmos bien conocidos. Seguramente obtendrá mejores resultados utilizando el patrón Divide & Impera, en lugar de simplemente iterar sobre las dos listas. Es solo una crítica sobre el patrón del algoritmo, de hecho me parece pertinente.

    – Lucas

    27 de febrero de 2010 a las 18:45

  • Yo también te voté. Esta es exactamente la parte de fusión de mergesort.

    – Larry

    27 de febrero de 2010 a las 19:00

  • Se trata de fusionar dos listas ordenadas. La segunda parte del ordenamiento por fusión es fusionar dos listas ordenadas. Es bastante sencillo.

    – Ross

    27 de febrero de 2010 a las 19:29

avatar de usuario
piccolbo

Entonces, al fusionar el ingenio 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 crédito por 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 compilador de optimización vea una recursión de cola aquí, pero yo sí. La sangría es un toque final.

  • Esta es exactamente la respuesta correcta, ¿por qué los votos negativos? @Luca: +1 de mí.

    – tzaman

    27 de febrero de 2010 a las 18:19


  • @tzaman: ¿Cómo diablos es esta una respuesta relacionada con esta pregunta?

    – fanfarrón

    27 de febrero de 2010 a las 18:33

  • @Bragaadeesh: ¿Tienes que ordenar? Me pregunto por qué no usar algoritmos bien conocidos. Seguramente obtendrá mejores resultados utilizando el patrón Divide & Impera, en lugar de simplemente iterar sobre las dos listas. Es solo una crítica sobre el patrón del algoritmo, de hecho me parece pertinente.

    – Lucas

    27 de febrero de 2010 a las 18:45

  • Yo también te voté. Esta es exactamente la parte de fusión de mergesort.

    – Larry

    27 de febrero de 2010 a las 19:00

  • Se trata de fusionar dos listas ordenadas. La segunda parte del ordenamiento por fusión es fusionar dos listas ordenadas. Es bastante sencillo.

    – Ross

    27 de febrero de 2010 a las 19:29

avatar de usuario
héroehuyongtao

Usa la recursividad. 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;
}

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad