Hiii ...lié problème de la liste
Si nous donne deux listes chaînées (peut être de longueur différente) de telle sorte que quelques noeuds de fin sont communs ... Comment pouvons-nous trouver le premier noeud commun dans le moins de temps possible ...?
Les listes sont liées individuellement. Certains nœuds sont communs à la fin et nous devons trouver le premier commun pour tous les deux de la fin.
En supposant que chaque liste liée a un ensemble complètement unique, la seule méthode que je vois est d'utiliser une boucle imbriquée qui serait terriblement inefficace. Si les ensembles de données ne sont pas uniques, vous pouvez utiliser un tiers (reliée) liste comme un cache de seulement nœuds uniques, mais vous cherchez toujours à un pire cas de O (n²)
+1 .... nous devrions aider en donnant pour la théorie pour la théorie, pas de code pour chaque théorie. Il pourrait ne jamais essayer de comprendre s'il obtient le code préparé pour sa question de devoir. – loxxy
Je suppose que je permettais les listes non triées et les correspondances qui ne sont pas dans le même "index". Cela nécessiterait O (n²) – Puddingfox
complexité total: O (n)
Par exemple:
1-> 2-> 3-> 4-> 7-> 8
--------- 5-> 6-> 7> 8
Nous prévoyons d'obtenir puisque c'est le premier nœud commun.
et si les deux listes avaient le même nombre d'éléments – TalentTuner
@saurabh, voulez-vous dire qu'ils n'ont aucun élément commun? Ou ils ont des éléments communs qui suivent des éléments non communs? – Elisha
@saurabh: alors vous sautez zéro élément avant de rechercher le premier élément commun (en vous rappelant de vérifier que les éléments suivants correspondent également). –
Une solution O (n) pour trouver le premier nœud dans l'une des listes avec la même valeur. Vous pouvez ensuite extraire la valeur de ce noeud.
Toutes les sections de code (commentaires) sont O(1) sauf indication contraire et aucune opération O(n) imbriquée. Donc la solution entière est O (n).
Cela fonctionne en comptant les éléments dans chaque liste puis en faisant avancer le pointeur pour la liste la plus longue afin que les extrémités soient alignées.
Ensuite, il parcourt les deux listes de manière synchronisée. Si les nœuds correspondent et n'ont pas correspondu précédemment, il enregistre ce nœud (et non juste s'ils correspondent car vous voulez que le le plus tôt correspond à dans une séquence). Si elles ne correspondent pas, vous enregistrez ce fait afin qu'une correspondance ultérieure soit considérée comme la plus précoce dans la séquence.Au moment où vous arrivez à la fin des deux listes, vous avez une indication qu'il n'y avait pas de correspondance (si le noeud final des deux listes est différent) ou la première correspondance dans la séquence.
pseudo-code seulement bien sûr, depuis sa devoirs:
def findCommonNode (head1, head2):
# Work out sizes O(n)
set count1 and count2 to 0
set ptr1 to head1
while ptr1 is not equal to NULL:
increment count1
set ptr1 to ptr1->next
set ptr2 to head2
while ptr2 is not equal to NULL:
increment count2
set ptr2 to ptr2->next
# If either size is 0, no match possible.
if count1 == 0 or count2 = 0:
return NULL
# Make the first list longer (or same size).
if count1 < count2:
swap count1 and count2
swap head1 and head2 (local copies only)
# Move through longest list until they're aligned O(n).
set ptr1 to head1
set ptr2 to head2
while count1 is greater than count2:
decrement count1
set ptr1 to ptr1->next
# Initially mark as non-match.
set retptr to NULL
# Process both (aligned) lists O(n).
while ptr1 is not equal to NULL:
# If equal and if first match after non-match, save position.
if ptr1->data is equal to ptr2.data:
if retptr is equal to NULL:
set retptr to ptr1
else:
# If not equal, mark as non-match.
set retptr to NULL
# Advance to next element in both lists.
set ptr1 to ptr1->next
set ptr2 to ptr2->next
# Return the earliest match.
return retptr
Disons que vous avez les deux listes 1,2,3,4,5,5,6,7,8,9 et 0,6,9,8,9. Et faire avancer les aligner la liste 1 pointeur en fonction de la différence de taille, vous obtiendrez:
v
1 2 3 4 5 5 6 7 8 9
0 6 9 8 9
^
Ensuite, vous définissez correspondance NULL et commencer le traitement. Ils ne correspondent pas (5/0) de sorte que vous définissez le premier nœud correspondant à NULL (même s'il est déjà NULL) et avancez à 6/6.
Ces (6/6) correspondent (et la correspondance actuelle est NULL) de sorte que vous enregistrez l'adresse de l'un d'entre eux comme le match, et l'avance.
7/9 ne correspond pas donc vous définissez à nouveau la correspondance sur NULL, puis avancez. Les correspondances et la correspondance est NULL, donc vous définissez à nouveau la correspondance avec l'un d'entre eux, puis avancez.
9/9 correspond également à mais est déjà défini, donc vous ne le changez pas. Avancez ensuite et votre hors des éléments dans les deux listes.
Vous renvoyez ensuite la correspondance avec l'un des nœuds 8. Et c'est votre premier match pour une section finale commune.
Est-ce que ces devoirs - ça sonne certainement comme ça. Veuillez marquer comme tel. –
Pas assez d'informations. Les listes sont-elles isolées ou doublement liées? Avez-vous un pointeur de queue? Qu'est-ce que "quelques nœuds de la fin sont communs" signifie exactement? Est-ce que «premier commun» signifie le plus proche de la tête ou le plus proche de la queue? –
Au moins essayer et trouver une réponse à vos devoirs d'abord, avant de poster ici. –