Comment trouver l'élément central de la liste chaînée en un seul passage?

L'une des questions les plus populaires concernant les structures de données et l'algorithme, principalement posée lors d'un entretien téléphonique.

En trichant, et en faisant deux passes en même temps, en parallèle. Mais je ne sais pas si les recruteurs vont aimer ça.

Peut être fait sur une seule liste chaînée, avec une belle astuce. Deux pointeurs parcourent la liste, un à double vitesse. Lorsque le rapide atteint la fin, l'autre est à mi-chemin.

S'il ne s'agit pas d'une liste doublement liée, vous pouvez simplement compter et utiliser une liste, mais cela nécessite de doubler votre mémoire dans le pire des cas, et cela ne fonctionnera tout simplement pas si la liste est trop grande pour être stockée en mémoire.

Une solution simple, presque stupide, consiste simplement à incrémenter le nœud du milieu tous les deux nœuds

function middle(start) {
    var middle = start
    var nextnode = start
    var do_increment = false;
    while (nextnode.next != null) {
        if (do_increment) {
             middle = middle.next;
        }
        do_increment = !do_increment;
        nextnode = nextnode.next;
    }
    return middle;
}

Élaboration de la réponse d'Hendrik

S'il s'agit d'une liste doublement liée, parcourez les deux extrémités

function middle(start, end) {
  do_advance_start = false;
  while(start !== end && start && end) {
     if (do_advance_start) {
        start = start.next
     }
     else {
        end = end.prev
     }
     do_advance_start = !do_advance_start
  }
  return (start === end) ? start : null;
}

Donné [1, 2, 3] => 2

1, 3
1, 2
2, 2

Donné [1, 2] => 1

1, 2
1, 1

Donné [1] => 1

Donné [] => null

Créez une structure avec un pointeur capable de pointer vers les nœuds de la liste liée et avec une variable entière qui tient compte du nombre de nœuds dans la liste.

struct LL{
    struct node *ptr;
    int         count;
}start;

Maintenant, stockez l'adresse du premier nœud de la liste liée dans et initialisez . Assurez-vous que la valeur de est incrémentée de un après la création réussie d'un nouveau noeud dans la liste liée. De même, décrémentez-le de un chaque fois qu'un nœud est supprimé de la liste chaînée.s t a r t . c o u n t = 1 s t a r t . c o u n $start.ptr$$start.count = 1$
$start.count$

Utilisez pour trouver l'élément central en une seule passe.$start.count$

Créez un tableau dynamique, où chaque élément du tableau est un pointeur vers chaque nœud de la liste dans l'ordre de déplacement, en commençant par le début. Créez un entier, initialisé à 1, qui garde une trace du nombre de nœuds que vous avez visités (qui augmente chaque fois que vous accédez à un nouveau nœud). Lorsque vous arrivez à la fin, vous savez quelle est la taille de la liste et vous disposez d'un tableau ordonné de pointeurs vers chaque nœud. Enfin, divisez la taille de la liste par 2 (et soustrayez 1 pour l'indexation basée sur 0) et récupérez le pointeur contenu dans cet index du tableau; si la taille de la liste est impaire, vous pouvez choisir quel élément renvoyer (je retournerai quand même le premier).

Voici du code Java qui fait passer le message (même si l'idée d'un tableau dynamique sera un peu chancelante). Je fournirais C / C ++ mais je suis très rouillé dans ce domaine.

public Node getMiddleNode(List<Node> nodes){

    int size = 1;
    //add code to dynamically increase size if at capacity after adding
    Node[] pointers = new Node[10];

    for (int i = 0; i < nodes.size(); i++){
        //remember to dynamically allocate more space if needed
        pointers[i] = nodes.get(i);
        size++;
    }

    return pointers[(size - 1)/2];

}

La récursivité est-elle considérée comme plus d'un passage?

Parcourez la liste jusqu'à la fin, en passant un nombre entier par référence. Faites une copie locale de cette valeur à chaque niveau pour référence ultérieure et incrémentez le nombre de références lors du prochain appel.

Sur le dernier nœud, divisez le nombre par deux et tronquez / floor () le résultat (si vous voulez que le premier nœud soit le "milieu" quand il n'y a que deux éléments) ou arrondissez (si vous voulez que le deuxième nœud soit le milieu"). Utilisez de manière appropriée un index à zéro ou à un.

En déroulant, faites correspondre le nombre de références à la copie locale (qui est le numéro du nœud). S'il est égal, renvoyez ce nœud; sinon retourne le nœud renvoyé par l'appel récursif.
.

Il existe d'autres façons de procéder; certains d'entre eux peuvent être moins encombrants (je pensais avoir vu quelqu'un dire de le lire dans un tableau et d'utiliser la longueur du tableau pour déterminer le milieu - bravo). Mais franchement, il n'y a pas de bonnes réponses, car c'est une question d'entrevue stupide. Numéro un, qui utilise toujours des listes chaînées ( opinion à l'appui ); Deuxièmement, trouver le nœud central est un exercice académique arbitraire sans valeur dans des scénarios réels; Troisièmement, si j'avais vraiment besoin de connaître le nœud intermédiaire, ma liste chaînée exposerait un nombre de nœuds. Il est plus facile de conserver cette propriété que de perdre du temps à parcourir toute la liste chaque fois que je veux le nœud central. Et enfin, quatre, chaque enquêteur va aimer ou rejeter des réponses différentes - ce qu'un enquêteur pense être lisse, un autre dira ridicule.

Je réponds presque toujours aux questions d'entrevue avec plus de questions. Si je reçois une question comme celle-ci (je n'en ai jamais), je demanderais (1) Que stockez-vous dans cette liste chaînée, et existe-t-il une structure plus appropriée pour accéder efficacement au nœud intermédiaire s'il y a vraiment un besoin de le faire ; (2) Quelles sont mes contraintes? Je peux le rendre plus rapide si la mémoire n'est pas un problème (par exemple la réponse du tableau), mais si l'intervieweur pense que le gonflement de la mémoire est un gaspillage, je serai sonné. (3) Dans quelle langue vais-je développer? Presque toutes les langues modernes que je connais ont des classes intégrées pour traiter les listes liées qui rendent la traversée de la liste inutile - pourquoi réinventer quelque chose qui a été réglé pour l'efficacité par les développeurs du langage?

En utilisant 2 pointeurs. Incrémentez un à chaque itération et l'autre à chaque seconde itération. Lorsque le premier pointeur pointe vers la fin de la liste chaînée, le second pointeur pointe vers le mode intermédiaire de la liste chaînée.