Question d'entretien : Fusionner deux listes chaînées triées sans créer de nouveaux noeuds

Question

Il s'agit d'une question de programmation posée lors d'un test écrit pour un entretien. "Vous avez deux listes singulièrement liées qui sont déjà triées, vous devez les fusionner et renvoyer la tête de la nouvelle liste sans créer de nouveaux nœuds supplémentaires. La liste retournée doit également être triée.

La méthode signat Node MergeLists(Node list1, Node list2) ;

La classe de nœuds est indiquée ci-dessous :

class Node{
    int data;
    Node next;
}

J'ai essayé de nombreuses solutions, mais le fait de ne pas créer de nœud supplémentaire ne fait que compliquer les choses. Merci de m'aider.

Voici l'article de blog qui l'accompagne http://techieme.in/merging-two-sorted-singly-linked-list/

Answer 1

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

Answer 2

La récursivité ne devrait pas être nécessaire pour éviter l'allocation d'un nouveau nœud :

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) {
    if (list1.next.data > list2.data) {
      Node tmp = list1.next;
      list1.next = list2;
      list2 = tmp;
    }
    list1 = list1.next;
  } 
  list1.next = list2;
  return head;
}

Answer 3

Node MergeLists(Node node1, Node 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;
      }
   }
   current.next = NULL // needed to complete the tail of the merged list
   return head;

}

Answer 4

Regardez maman, pas de récursivité !

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

Answer 5

Voici l'algorithme permettant de fusionner deux listes chaînées triées A et 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

Ici, C sera la liste de sortie.