O (n) решение для поиска первого узла в одном из списков с тем же значением.Затем вы можете извлечь значение из этого узла.
Все разделы кода (комментарии) имеют значение O(1), если не указано иное, и вложенных операций O(n) нет.Следовательно, все решение - O (n).
. Оно работает путем подсчета элементов в каждом списке, а затем передвигает указатель для самого длинного списка, чтобы концы были выровнены.
Затем он проходит черезоба списка синхронизированы.Если узлы совпадают и ранее не сопоставлялись, он сохраняет этот узел (, а не , только если они совпадают, поскольку вы хотите, чтобы самое раннее совпадение в последовательности).
Если они не совпадают, вы сохраняете этот факт, так что последующее совпадение будет считаться самым ранним в последовательности.
К тому времени, как вы дойдете до конца обоих списков, у вас либо появится указание на то, чтоне было совпадения (если последний узел обоих списков различен) или самое раннее совпадение в последовательности.
Конечно, только псевдокод, поскольку это домашняя работа:
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
Допустим,у вас есть два списка 1,2,3,4,5,5,6,7,8,9 и 0,6,9,8,9.Выровняв их и продвинув указатель списка 1 на основе разницы в размере, вы получите:
v
1 2 3 4 5 5 6 7 8 9
0 6 9 8 9
^
Затем установите соответствие NULL и начните обработку.Они не совпадают (5/0), поэтому вы устанавливаете первый соответствующий узел на NULL (даже если он уже равен NULL) и переходите к 6/6.
. Эти (6/6) совпадают (итекущее совпадение равно NULL), поэтому вы сохраняете адрес одного из них в качестве совпадения и продвигаетесь.
7/9 не совпадает, поэтому вы снова устанавливаете совпадение в NULL, а затем продвигаетесь.
8/8 совпадений, и совпадение равно NULL, поэтому вы снова устанавливаете совпадение для одного из них, затем переходите к следующему.
9/9 также соответствует , но совпадение уже установлено, поэтому выне меняй это.Затем продвиньтесь вперед и вы выйдете из элементов в обоих списках.
Затем вы вернете совпадение с одним из 8 узлов.И это самое раннее совпадение с общим трейлингом.