Wie finde ich das mittlere Element der verknüpften Liste in einem Durchgang?

12

Eine der beliebtesten Fragen aus den Bereichen Datenstruktur und Algorithmus, die meistens beim Telefoninterview gestellt werden.

Gilles 'SO - hör auf böse zu sein'
quelle
5
Wenn die Antworten in diesem Thread den Erwartungen des Interviewers entsprechen, testet diese Frage nicht die technischen Fähigkeiten, sondern wie gut der Kandidat wie ein Anwalt ausweichen kann.
G. Bach
2
Dies ist eine schreckliche Interviewfrage, weil sie kritisch vom Begriff " bestanden " abhängt, der vage, mehrdeutig und subjektiv ist. Bei fast allen guten Antworten auf diese Frage wird die Definition missbraucht, damit Sie sie effektiv ignorieren können.
RBarryYoung
2
Nun, die Frage wirft hier viele Diskussionen auf. Das bedeutet, dass es in einer Hinsicht eine gute Interviewfrage ist: Es bringt Sie zum Nachdenken.
Hendrik Jan
3
Ich möchte also antworten: "Lies alle Elemente in einen Vektor und greife dann auf das Element an der Position size () / 2 zu."
Cort Ammon
1
@HendrikJan Eigentlich denke ich, dass es eine völlig schreckliche Interviewfrage ist. Erstens wird es wahrscheinlich zu Auseinandersetzungen darüber kommen, was genau "in einem Durchgang" bedeutet, anstatt zu einer produktiven Diskussion. Zweitens könnte ein Kandidat die "richtige" Antwort finden und sie dann ablehnen, weil er der Meinung ist, dass sie das Kriterium "in einem Durchgang" verletzt. Drittens, weil es eine bekannte Frage ist, ist es ein besserer Test für "Kennst du beliebte Interviewfragen?" als "Bist du gut für diesen Job?" Jeder von ihnen sollte ausreichen, um dies als Frage zu betrachten. Alle drei gleichzeitig sind eine Katastrophe.
David Richerby

Antworten:

24

Durch Schummeln und zwei Durchgänge gleichzeitig, parallel. Aber ich weiß nicht, ob das den Personalvermittlern gefallen wird.

Kann mit einem netten Trick auf einer einzelnen verknüpften Liste ausgeführt werden. Zwei Zeiger bewegen sich über die Liste, einer mit doppelter Geschwindigkeit. Wenn der Schnelle das Ende erreicht, ist der andere auf halbem Weg.

Hendrik Jan
quelle
1
Ja, es ist unklar, ob dies ein einzelner Durchgang ist. Die Frage ist in diesem Punkt unklar.
David Richerby
2
Dies hängt übrigens mit dem Rätsel zusammen, bei dem Sie zwei Kerzen haben, von denen jede eine Stunde brennt, und Sie aufgefordert werden, 45 Minuten zu messen.
Hendrik Jan
2
Ist das wirklich etwas anderes, als die Liste zu iterieren, Elemente zu zählen und ein zweites Mal bis zur Hälfte zu iterieren? Alles, was anders ist, ist, wenn Sie die zusätzliche Hälfte wiederholen. Wie @RBarryYoung auf der anderen, ähnlichen Antwort erwähnt, handelt es sich nicht um einen einzelnen Durchgang, sondern um eineinhalb Durchgänge.
2
Wenn die Liste lang ist, führt das Verschieben beider Zeiger "parallel" zu weniger Cache-Fehlern als ein zweites Mal von Anfang an.
zwol
2
Hierbei wird dasselbe Prinzip wie beim Schildkröten- und Hasenalgorithmus für die Zykluserkennung verwendet.
Joshua Taylor
7

Wenn es sich nicht um eine doppelt verknüpfte Liste handelt, können Sie einfach eine Liste zählen und verwenden. Dies erfordert jedoch im schlimmsten Fall eine Verdoppelung des Arbeitsspeichers, und es funktioniert einfach nicht, wenn die Liste zu groß ist, um im Arbeitsspeicher gespeichert zu werden.

Eine einfache, fast alberne Lösung besteht darin, den mittleren Knoten alle zwei Knoten zu erhöhen

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;
}
00500005
quelle
Ihre zweite Option ist die richtige Antwort (IMHO natürlich).
Matthew Crumley
1
Es passiert tatsächlich 1 1/2 Pässe über die verknüpfte Liste.
RBarryYoung
6

Auf Hendriks Antwort eingehen

Wenn es sich um eine doppelt verknüpfte Liste handelt, iterieren Sie an beiden Enden

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

Gegeben [1, 2, 3] => 2

1, 3
1, 2
2, 2

Gegeben [1, 2] => 1

1, 2
1, 1

Gegeben [1] => 1

Gegeben [] => null

00500005
quelle
Wie ist das effizient? Sie iterieren auch n-mal und nicht n / 2.
Karan Khanna
3

Erstellen Sie eine Struktur mit einem Zeiger, der auf Knoten der verknüpften Liste zeigen kann, und einer Ganzzahlvariablen, die die Anzahl der Knoten in der Liste zählt.

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

steinrt.ptrsteinrt.cÖunt=1
steinrt.cÖunt

steinrt.cÖunt

Prateek
quelle
-2

Erstellen Sie ein dynamisches Array, bei dem jedes Element des Arrays beginnend mit dem Anfang ein Zeiger auf jeden Knoten in der Liste ist. Erstellen Sie eine auf 1 initialisierte Ganzzahl, die protokolliert, wie viele Knoten Sie besucht haben (die sich jedes Mal erhöht, wenn Sie zu einem neuen Knoten wechseln). Wenn Sie am Ende angelangt sind, wissen Sie, wie groß die Liste ist, und Sie haben ein geordnetes Array von Zeigern auf jeden Knoten. Teilen Sie abschließend die Größe der Liste durch 2 (und subtrahieren Sie 1 für die 0-basierte Indizierung) und rufen Sie den Zeiger ab, der in diesem Index des Arrays enthalten ist. Wenn die Größe der Liste ungerade ist, können Sie auswählen, welches Element zurückgegeben werden soll (das erste Element werde ich weiterhin zurückgeben).

Hier ist etwas Java-Code, der den Punkt vermittelt (auch wenn die Idee eines dynamischen Arrays ein bisschen wackelig sein wird). Ich würde C / C ++ zur Verfügung stellen, aber ich bin in diesem Bereich sehr rostig.

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

}
Andonaeus
quelle
-3

Wird eine Rekursion als mehr als ein Durchgang betrachtet?

Durchlaufen Sie die Liste bis zum Ende und übergeben Sie eine Ganzzahl als Referenz. Erstellen Sie auf jeder Ebene eine lokale Kopie dieses Werts, um später darauf zu verweisen, und erhöhen Sie die Ref-Anzahl, die beim nächsten Aufruf verwendet wird.

Teilen Sie die Anzahl auf dem letzten Knoten durch zwei und kürzen Sie / floor () das Ergebnis (wenn Sie möchten, dass der erste Knoten die "Mitte" ist, wenn es nur zwei Elemente gibt) oder runden Sie auf (wenn Sie möchten, dass der zweite Knoten ist) die Mitte"). Verwenden Sie einen auf Null oder Eins basierenden Index entsprechend.

Ordnen Sie die Anzahl der Referenzen der lokalen Kopie zu (dies ist die Nummer des Knotens). Wenn gleich, geben Sie diesen Knoten zurück. else return Der vom rekursiven Aufruf zurückgegebene Knoten.
.

Es gibt andere Möglichkeiten, dies zu tun. Einige von ihnen sind möglicherweise weniger umständlich (ich dachte, ich hätte jemanden sagen sehen, der es in ein Array einliest und die Array-Länge verwendet, um das mittlere Lob zu bestimmen). Aber ehrlich gesagt gibt es keine guten Antworten, denn es ist eine blöde Interviewfrage. Nummer eins, die immer noch verknüpfte Listen verwendet ( unterstützende Meinung ); Zweitens ist das Finden des mittleren Knotens eine willkürliche, akademische Übung, die in realen Szenarien keinen Wert hat. Drittens, wenn ich den mittleren Knoten wirklich kennen müsste, würde meine verknüpfte Liste eine Knotenzahl anzeigen. Es ist hella einfacher, diese Eigenschaft beizubehalten, als jedes Mal, wenn ich den mittleren Knoten möchte, Zeit zu verschwenden, um die gesamte Liste zu durchlaufen. Und schließlich, vier, wird jeder Interviewer unterschiedliche Antworten mögen oder ablehnen - was ein Interviewer für schlau hält, wird ein anderer für lächerlich halten.

Ich beantworte Interviewfragen fast immer mit mehr Fragen. Wenn ich eine solche Frage bekomme (habe ich nie), würde ich fragen: (1) Was speichern Sie in dieser verknüpften Liste, und gibt es eine geeignetere Struktur, um effizient auf den mittleren Knoten zuzugreifen, wenn dies wirklich erforderlich ist ; (2) Was sind meine Einschränkungen? Ich kann es schneller machen, wenn der Speicher kein Problem darstellt (z. B. die Array-Antwort), aber wenn der Interviewer den Eindruck hat, dass Speicherplatz verschwenderisch ist, werde ich süchtig. (3) In welcher Sprache werde ich mich entwickeln? Nahezu jede moderne Sprache, die ich kenne, verfügt über integrierte Klassen für den Umgang mit verknüpften Listen, die das Durchlaufen der Liste unnötig machen. Warum etwas neu erfinden, das von den Entwicklern der Sprache auf Effizienz hin optimiert wurde?

James K
quelle
6
Sie wissen nicht, wer was herabgestimmt hat, und Ihre Schlussfolgerung, dass eine Person alles herabgestimmt hat, mag wahr sein oder auch nicht, aber es gibt sicherlich keine Grundlage für Fakten, die Ihnen zur Verfügung stehen. Aber ich stimme Ihrer Antwort nicht zu, weil wir nach Erklärungen suchen, nicht nach Code-Haufen.
David Richerby
Es mag eine Vermutung sein, aber wenn ich einen Moment und weniger als 30 Sekunden später nachschaue, hat jeder Beitrag genau -1, es ist keine unvernünftige. Selbst wenn es 5 oder 6 verschiedene Personen waren, hat keiner von ihnen einen Kommentar hinterlassen, warum. Aber danke, dass du wenigstens einen Grund angibst. Ich verstehe nicht, warum eine wortreiche Erklärung besser ist als Code - ja, es ist für ein Telefoninterview, aber ich gebe dem OP keine vorgefertigte Antwort zum Aufstoßen, ich zeige ihm einen Weg, dies zu tun. IE Ich denke, einen Beitrag runter zu stimmen, weil er Code hat, ist unangebracht, aber danke, dass du zumindest sagst, warum du das getan hast.
James K
Fairer Punkt - mir war nicht in den Sinn gekommen, dass Sie den Zeitpunkt der Abstimmungen kennen (das Laden der Seite während der Abstimmungen ist meiner Meinung nach der einzige Weg, wie normale Benutzer wie wir das herausfinden können). Wir haben ein paar Meta-Posts darüber, warum wir versuchen, tatsächlichen Code hier zu vermeiden: (1) (2) .
David Richerby
Danke für die Meta-Links. Ich habe die FAQ gelesen, aber ich habe dort nichts gesehen - nicht, dass mir so etwas aufgefallen wäre, höchstwahrscheinlich nicht, was ich erwartet hätte. Aber ich konnte auch nichts finden, als ich nach dem Beulen noch einmal nachprüfte. Ich kann es immer noch übersehen, aber ich habe geschaut. Die Argumentation in den Metapostings ist sinnvoll; Danke für die Antwort.
James K
-5

Mit 2 Zeigern. Inkrementieren Sie eine bei jeder Iteration und die andere bei jeder zweiten Iteration. Wenn der erste Zeiger auf das Ende der verknüpften Liste zeigt, zeigt der zweite Zeiger auf den mittleren Modus der verknüpften Liste.

b dharuni
quelle
Dies entspricht genau der Antwort von Hendrick . Bitte antworten Sie nicht, es sei denn, Sie haben etwas Neues zu sagen.
David Richerby