Datenstrukturen verknüpfte Liste

Question

Ich wurde gebeten, dies zu lösen:

Es gibt zwei einfach verknüpfte Listen. Ich muss eine Methode schreiben, die diese beiden verknüpften Listen abrufen und einen Zeiger auf den Startpunkt zurückgeben, wo das Suffix in diesen beiden Listen identisch ist.

Beispiel:

gegeben:

1->2->4->6->8->10->15 
2->4->8->10->15 

der zurückgegebene Wert würde ein Zeiger auf das Mitglied sein - 8.

Aber ich brauche es zu tun, ohne die Listen zu ändern oder mit mehr Speicher, und - wir müssen die Listen nur einmal scannen, bedeutet T(n)=O(n).

Answer 1

1. messen die Längen der beiden Listen
2. überspringen vorwärts in der längeren Liste, bis sie die gleiche Länge
3. zu Fuß nach vorn durch beide Listen in Schritt, und erinnere mich an die Knoten nach dem letzten Punkt, an dem die Listen sind haben unterschiedliche Elemente. Dies sind die Zeiger, die Sie zurückgeben können.

Nun ... Ich weiß, Sie sagten, dass Sie nur die Listen einmal scannen möchten, und ich habe es zweimal getan, aber man auch gesagt, dass dies bedeutet T (n) = O (n), und das ist nicht korrekt.

die Listen zweimal Scannen ist auch in O (n) und ist erforderlich, um das Problem ohne die Verwendung von unbeschränkten zusätzlichen Speicher zu lösen.

Answer 2

Dies ist ein psuedocode .. nicht Python-Code für diese Angelegenheit die beiden Listen zu nehmen und p1 Punkt auf längere Liste und p2 Punkt auf kürzere Liste,

while p1->next!=NULL: 
    if p1->value = p2->value: 
     p1 = p1->next 
     p2 = p2->next 
    else: 
     p1 = p1->next 
     returnpointer = p1->next// if it happens that some elements are same towards end but not the last element.. p1->next would be pointing to NULL anyways and else.. it'll always be the element next to the last element which wasn't same 
return returnpointer