Ich habe zwei verkettete Listen, die die Ziffern der Dezimalzahlen in der Reihenfolge von den meisten bis zu den niedrigstwertigen Stellen darstellen. für zB 4->7->9->6 und 5->7
Die Antwort sollte 4->8->5->3 lauten, ohne die Listen umzukehren, da das Umkehren der Listen zu einer Verringerung der Effizienz führen würde.
Ich denke über das Lösen des Problems mit stack.Ich werde beide Listen durchqueren und die Datenelemente in zwei separate Stapel schieben.Ein für jede verknüpfte Liste.Thier ich beide Stapel zusammen und füge beide Elemente hinzu und wenn die Ergebnis ist eine zweistellige Nr I 10 modulo es und speichern Sie den Übertrag in einer Variablen temp. Der Rest wird im Knoten gespeichert und der Übertrag wird zur nächsten Summe hinzugefügt und so weiter. wenn die zwei Stapel s1 und s2 sind und die Ergebnisliste ist res.
%Vor%Ich bin in Vorstellungsgesprächen oft auf dieses Problem gestoßen, aber das ist die beste Lösung, die ich mir vorstellen kann. Wenn jemand mit etwas effizienterem in c kommen kann, werde ich sehr froh sein.
Zwei Durchgänge, kein Stapel:
Ermittelt die Länge der beiden Listen.
Erstellen Sie eine Lösungsliste mit einem Knoten. Initialisiere den Wert dieses Knotens auf Null. Dies wird die Carry-Ziffer enthalten. Setzen Sie einen Listenzeiger (nennen Sie es den Übertragszeiger) auf den Speicherort dieses Knotens. Setzen Sie einen Listenzeiger (nennen Sie es den Endzeiger) auf die Position dieses Knotens.
Beginnen Sie mit der längeren Liste, indem Sie für jeden überschüssigen Knoten einen neuen Knoten mit dem Endzeiger verknüpfen und ihm den Wert des überschüssigen Knotens zuweisen. Setzen Sie den Endzeiger auf diesen neuen Knoten. Wenn die Wert ist kleiner als 9, setzen Sie den Übertragszeiger auf den neuen Knoten.
Jetzt haben wir beide Listenzeiger mit der gleichen Anzahl von Knoten in jedem.
Während die Listen nicht leer sind ...
Verknüpfen Sie einen neuen Knoten mit dem Endzeiger und verschieben Sie den Endzeiger auf diesen Knoten.
Ermittelt die Werte aus jeder Liste und bringt jeden Listenzeiger zum nächsten Knoten.
Fügen Sie die zwei Werte zusammen.
Wenn der Wert größer als neun ist, setzen Sie den Wert auf value mod 10 , inkrementieren Sie den Wert, der im Knoten des Übertragszeigers gehalten wird, und verschieben Sie den Übertragszeiger zum nächsten Knoten. Wenn der Wert des Übertragszeigers neun ist, setze er auf Null und gehe zum nächsten Knoten.
Wenn der Wert neun ist. Stell es ein. Tun Sie nichts anderes.
Wenn der Wert kleiner als neun ist. Stell es ein. Setze den Zeiger auf den aktuellen Knoten.
Wenn Sie mit beiden Listen fertig sind, prüfen Sie, ob der Knotenwert des Lösungszeigers Null ist. Ist dies der Fall, setzen Sie den Lösungszeiger auf den nächsten Knoten und löschen Sie die unnötige zusätzliche Ziffer.
So würde ich das Problem lösen:
Schritt 1: Führe beide verknüpften Listen durch, finde Längen
sagen len(L1) = m and len(L2) = n
Schritt 2: Finden Sie Längenunterschiede
%Vor%Schritt 3: Verschieben Sie einen temporären Zeiger d vor die größere Liste
Schritt 4: Nun haben wir zwei verkettete Listen zum Hinzufügen, deren Längen gleich sind, also addiere sie rekursiv und behalte einen Übertrag bei.
Schritt 5: ( Hinweis: if (d == 0) führt diesen Schritt nicht durch)
Nach Schritt 4 haben wir eine Teilausgabeliste, und jetzt müssen wir den Rest der größeren Liste am Anfang der Ausgabeliste platzieren.
%Vor%Hinweis: Ich löse das Problem, wie es mir vorgebracht wurde, nicht indem ich die Änderung der zugrunde liegenden Datenstruktur vorschlage.
Zeitkomplexität:
O(m+n)
O(n) , angenommen m > n
O(d)
Gesamt: O( (m+n) + (n) + (d) ) ODER O(m+n)
Raumkomplexität:
O(n) , Laufzeitstapelspeicher O(d) , Laufzeitstapelspeicher Gesamt: O(n + d) ODER O(n)
Ich würde nur den Gesamtwert jeder verknüpften Liste separat finden, sie zusammen addieren und dann diese Nummer in eine neue verknüpfte Liste umwandeln. So wandeln Sie 4- & gt; 7- & gt; 9- & gt; 6 und 5- & gt; 7 in Ganzzahlen mit den Werten 4796 bzw. 57 um. Addiere diese zusammen, um 4853 zu erhalten, dann transformiere das in eine verknüpfte Liste, die 4- & gt; 8- & gt; 5- & gt; 3 enthält. Sie können die Transformationen mit einfacher Mathematik durchführen.
Es wäre viel einfacher, es auf Ihre Art zu tun, wenn Sie die Art ändern würden, in der die Zahlen an erster Stelle stehen. Machen Sie es so, dass die Einerstelle immer zuerst steht, gefolgt von der Zehnerstelle, gefolgt von Hunderter usw.
BEARBEITEN: Da Sie scheinbar enorme Zahlen verwenden: Haben Sie darüber nachgedacht, doppelt verknüpfte Listen zu erstellen? Dann müssten Sie es nicht per se umkehren. Gehe einfach rückwärts.
Die Verwendung eines Stacks ist nicht effizienter als das Umkehren der Listen (tatsächlich ist das Umkehren der Listen). Wenn Ihr Stack-Objekt dynamisch zugewiesen wird, ist dies kein großes Problem, aber wenn Sie es mit einer Aufrufrekursion erstellen, erhalten Sie leicht Stack Overflow der schlechten Sortierung. : -)
Tags und Links c linked-list