82 votos

Entrevista: la Fusión de dos Ordenan por separado Lista Enlazada

Esta es una programación de pregunta durante una prueba escrita para una entrevista. "Usted tiene dos listas ligadas sencillas que ya están ordenados, usted tiene que combinar y volver la cabeza de la lista de nuevo sin crear nuevos nodos adicionales. La lista devuelta debe ordenarse así"

La firma del método es: Nodo MergeLists(Nodo list1, el Nodo lista2);

Nodo de la clase es el siguiente:

class Node{
    int data;
    Node next;
}

He intentado muchas soluciones, pero no la creación de un nodo adicional tornillos de las cosas. Por favor, ayudar.

188voto

Stefan Haustein Puntos 4458
Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  if (list1.data < list2.data) {
    list1.next = MergeLists(list1.next, list2);
    return list1;
  } else {
    list2.next = MergeLists(list2.next, list1);
    return list2;
  }
}

115voto

Stefan Haustein Puntos 4458

La recursividad no debe ser necesaria para evitar la asignación de un nuevo nodo:

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  Node head;
  if (list1.data < list2.data) {
    head = list1;
  } else {
    head = list2;
    list2 = list1;
    list1 = head;
  }
  while(list1.next != null && list2 != null) {
    if (list1.next.data > list2.data) {
      Node tmp = list1.next;
      list1.next = list2;
      list2 = tmp;
    }
    list1 = list1.next;
  } 
  if (list1.next == null) list1.next = list2;
  return head;
}

12voto

Ben Puntos 31
Node MergeLists(Node node1, node2)
{
   if(node1 == null)
      return node2;
   else (node2 == null)
      return node1;

   Node head;
   if(node1.data < node2.data)
   {
      head = node1;
      node1 = node1.next;
   else
   {
      head = node2;
      node2 = node2.next;
   }

   Node current = head;
   while(node1 != null && node2 != null)
   {
      if(node1 == null) {
         current.next = node2;
         return head;
      }
      else if (node2 == null) {
         current.next = node1;
         return head;
      }

      if(node1.data < node2.data)
      {
          current.next = node1;
          current = current.next;

          node1 = node1.next;
      }
      else
      {
          current.next = node2;
          current = current.next;

          node2 = node2.next;
      }
   }

   return head;

}

4voto

Jaguar Puntos 8451

Aquí es el algoritmo sobre cómo combinar dos ordenados en listas enlazadas a y B:

while A not empty or B not empty:
   if first element of A < first element of B:
      remove first element from A
      insert element into C
   end if
   else:
      remove first element from B
      insert element into C
end while

Aquí C será la lista de salida.

4voto

wildplasser Puntos 17900

Look ma, no recursividad!

struct llist * llist_merge(struct llist *one, struct llist *two, int (*cmp)(struct llist *l, struct llist *r) )
{
struct llist *result, **tail;

for (result=NULL, tail = &result; one && two; tail = &(*tail)->next ) {
        if (cmp(one,two) <=0) { *tail = one; one=one->next; }
        else { *tail = two; two=two->next; }
        }
*tail = one ? one: two;
return result;
}

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X