объединенный связанный список в C

Question

Этот вопрос был задан мне в интервью: Есть два заголовка из двух связанных списков. В объединенном списке есть объединенный список, где во втором связанном списке в какой-то момент сливается первый. Как мы можем определить точку слияния и какова сложность нахождения этой точки?

Не могли бы вы помочь?

Answer 1

О (п)

search = list1->header; 
if (mixed->header == list1->header) search = list2->header; 

while (mixed->next != search) mixed = mixed->next; 

---

Edit: новое имя для переменных и несколько комментариев

/* search is what we want to find. Here it's the head of `list2` */ 
search = list2->header; 
/* unless the merging put `list2` first; then we want to search for `list1` */ 
if (mixed->header == list2->header) search = list1->header; 

/* assume (wrongly) that the header for the mixed list is the merge point */ 
mergepoint = mixed->head; 

/* traverse the mixed list until we find the pointer we're searching */ 
while (mergepoint->next != search) mergepoint = mergepoint->next; 
/* mergepoint now points to the merge point */ 

Answer 2

Update: Это предполагают, что Y-образное соединение двух связанных списков, как описано выше в сообщении Стив Джессопа. Но я думаю, что описание проблемы достаточно неоднозначно, что возможны различные интерпретации, из которых это только одно.

Это может быть сделано одним проходом по одному списку плюс частичный проход через другой. Другими словами, это O (n).

Вот предложил мой алгоритм:

Создать HashMap. (Да, это занятие на C, если у вас нет библиотеки, удобной для нее). Ключи будут указателями на элементы в List1 (то есть указатель на голову и каждую ссылку). Значения будут целыми числами, обозначающими позицию, то есть расстояние от главы List1.

Пробег через List1, отслеживая положение и хеш всех ваших указателей и положений.

Запуск через List2, отслеживание положения и поиск первого указателя, который встречается в хэшмапе.

На этом этапе вы узнаете позицию в списке2 первого узла, общего для обоих списков. Запись hashmap также будет содержать позицию в List1 этого же узла. Это прекрасно идентифицирует вашу точку слияния.

Answer 3

Вы хотите сказать, у вас есть Y-образную форму, как это:

песни1: A -> B -> C -> D -> E -> F

песни2: X -> Y - > Z -> E -> F

Где A .. Z - узлы узловых узлов. Мы хотим найти «точку слияния» E, которая определена как первый узел, появляющийся в обоих списках. Это верно?

Если это так, то я бы привязал последний узел списка2 (F) к первому узлу списка2 (X). Это превращает List2 в петлю:

list2: X -> Y -> Z -> E -> F -> X -> ...

Но что еще более важно:

песни1: A - > B -> C -> D -> E -> F -> X -> Y -> Z -> E -> ...

Это уменьшает вопрос до a previously-solved problem, который может быть разрешен в O (n) и O (1) дополнительном хранилище.

Но, читая свой вопрос, еще одна возможность заключается в том, что «слияние» означает «вставить». Таким образом, у вас есть два списка, как это:

песни1: A -> B -> C

песни2: D -> E -> F

, а затем другой полностью отдельный список:

песни3 : A -> B -> D -> E -> F -> C

где это время, A .. F - значения, содержащиеся в списке, а не сами узлы.

Если значения все разные, вам просто нужно найти список3 для D (или для более поздних версий D и A, если вы не знаете, какой список он был скопирован в другой). Это кажется бессмысленным вопросом. Если значения могут быть повторены, то вам нужно проверить полную последовательность list2 внутри list3. Но только потому, что вы находите «DEF», это не значит, что здесь был вставлен список2 - возможно, «DEF» уже несколько раз встречался в списке1, и вы только что нашли первый из них. Например, если я вставляю «DEF» в «ABCDEF», а результатом является «ABCDEFDEF», то я вставлял ли я индекс 3 или индекс 6? Невозможно сказать, поэтому на вопрос нельзя ответить.

Итак, в заключение, я не понимаю вопроса. Но я мог бы ответить на него в любом случае.

Answer 4

Если вопрос означает list2, содержащийся в списке1 (то есть list2 указывает где-то посередине списка1), то это легко - просто пройдите list1 и сравните указатели, пока не достигнете списка2.

Однако такая интерпретация не имеет большого смысла, поскольку, вставив list2 в список1 (например, 1 1 2 2 1), вы также измените list2 - последний 1 станет частью списка2.

Таким образом, я предполагаю, что вопрос о форме Y:

песни1: A -> B -> C -> D -> E -> F

list2: X -> Y -> Z -> E -> F

Это можно решить с помощью хеш-таблицы, как предложил Карл.

Решение без хэш- бы это:

1. Walk песни1 и отключить все свои указатели, как вы идете
2. Walk List2. Когда он заканчивается, вы достигли точке соединения
3. Ремонта указателей в list1

отсоединение и ремонт указатели в list1 можно сделать легко с помощью рекурсии:

Diconnect(node) 
{ 
    if (node->next == NULL) 
     walk list2 to its end, that is the solution, remember it 
    else 
    { 
     tmp = node->next; 
     node->next = NULL; 
     Disconnect(tmp); 
     node->next = tmp; // repair 
    } 
} 

Позовите Disconnect (list1).

Это рекурсия вниз по списку1 и отключить указатели. Когда вы достигнете цели, выполните шаг 2 (перейдите в список 2, чтобы найти соединение), указатели на возврат при возврате из рекурсии.

Это решение временно изменяет список1, поэтому оно не является потокобезопасным, и вы должны использовать блокировку вокруг вызова Disconnect (list1).

Answer 5

Извините, если мой ответ кажется слишком простым, но если у вас есть два связных список, которые идентифицируются с помощью заголовка и вы присоединиться к ним, так что

A -> B -> C -> D является первым списком, и

1 -> 2 -> 3 -> 4 является второй, то предположим

A -> B -> C -> 1 -> 2 -> 3 -> 4 -> D является результатом

затем, чтобы найти точку слияния, вы должны пройти окончательный список, пока не найдете второй заголовок (1). Что происходит в O (n1) наихудшем случае, где n1 - количество элементов первого списка (это происходит, если второй список объединяется в конце).

Вот как я хотел бы задать вопрос. Ссылка на язык C, вероятно, означала бы, что у вас нет «объекта» или предварительно упакованной структуры данных, если не указано.

[обновление], как предложил Себастьян, если два списка выше имеют одинаковые элементы, мое решение не будет работать. Я подозреваю, что именно здесь вступает в действие язык C: вы можете найти адрес первого элемента второго списка (голова). Таким образом, возражение дубликатов не будет выполнено.

Answer 6

Ну, есть несколько подходов для решения этой проблемы.

Обратите внимание, что я только обсуждаю подходы [corner cases may need to be handled separately], начиная с грубой силы и заканчивая лучшим.
Учитывая N: количество узлов в первом связанном списке
М: число узлов второго связанного списка

подход 1:
Сравнить каждый узел первого связанного списка с каждым другим узлом второго списка. Остановитесь, когда найдете соответствующий узел, это точка слияния.

while(head1) 
{ 
cur2=head2; 
while(cur2) 
{ 
    if(cur2==head1) 
     return cur2; 
    cur2=cur2->next; 
} 
head1=head1->next; 
} 

Время Сложность: O (N * M)
Пространство Сложность: O (1)

Подход 2:
Поддержание двух стеков. Нажимайте все узлы первого связанного списка до первого стека. Повторите его для второго связанного списка.
Начните выскакивать узлы из обоих стеков до тех пор, пока оба всплывающих узла не совпадут. Последний соответствующий узел является точкой слияния.
Время Сложность: O (N + M)
Пространство Сложность: O (N + М)

Подход 3: Использование
Марка хэш-таблицы. Вставьте все узлы первого связанного списка в хэш.
Поиск первого совпадающего узла второго списка в хэше.
Это точка слияния.
Время Сложность: O (N + M)
Space Сложность: O (N)
Следует отметить, что сложность пространства может изменяться в зависимости от используемой хэш-функции [говорить о С, где, как предполагается реализовать свой собственный хэш функция].

Подход 4:
Вставьте все узлы первого связанного списка [узлами, я имею в виду адреса] в массив.
Сортируйте массив с некоторым стабильным алгоритмом сортировки в O (N logN) времени [Сортировка слияния будет лучше].
Теперь найдите первый соответствующий узел из второго связанного списка.
Время Сложность: O (N LogN)
Пространство Сложность: O (N)
Следует отметить, что этот подход может быть лучше, чем Approach 3 [с точки зрения пространства], как он не использует хэш.

подход 5:
1. Взять массив размера M + N.
2. Вставьте каждый узел из первого связанного списка, а затем вставьте каждый узел из второго связанного списка.
3. Поиск первого повторяющегося элемента [можно найти в одном сканировании в режиме O (M + N)].
Время Сложность: O (N + M)
Пространство Сложность: O (N + М)

Подход 6: [A better approach]
1. Изменение первого связанного списка & сделать его круглым.
2. Теперь, начиная с заголовка второго связанного списка, найдите начало цикла, используя Floyd- Warshall cycle detection algorithm.
3. Удалите петлю [можно легко удалить, поскольку мы знаем последний узел].
Время Сложность: O (N + M)
Пространство Сложность: O (1)

подход 7: [Probably the best one]
1. Подсчитайте число узлов в первом связанном списке [с1 говорят ].
2. Подсчитайте количество узлов во втором связанном списке [say c2].
3. Найдите разницу [Давайте скажем c1> c2] diff = c1-c2.
4. Возьмите два указателя p1 & p2, p1, указывающий на головку первого связанного списка & p2, указывающий на головку второго связанного списка.
5. Переместить разность p1.
6.Перемещайте оба p1 & p2 каждый узел за раз, пока оба не указывают на один и тот же узел.
7. p1 или p2 указывает точку слияния.
Время Сложность: O (N + M)
Пространство Сложность: O (1)

Answer 7

тривиальное решение, очевидно, O (N + M). Хм .. Что может быть лучше. Вы можете перейти от начала до конца списка или наоборот. Когда у вас есть потоки, вы можете пойти по этим направлениям в какое-то время, так что бит должен быть быстрее.

Answer 8

// попробуйте этот код для слияния

void mergeNode(){ 
      node *copy,*current,*current1; 

      free(copy); 
     merge=NULL; 
    current=head; 
    current1=head1; 
    while(current!=NULL){ 
    if(merge==NULL){ 
     node *tmp; 
     tmp=(node*)malloc(sizeof(node)); 
     tmp->data=current->data; 
     tmp->link=NULL; 
     merge=tmp; 
    } 
    else{ 
     copy=merge; 
     while(copy->link!=NULL) 
      copy=copy->link; 
     node *tmp; 
     tmp=(node*)malloc(sizeof(node)); 
     tmp->data=current->data; 
     tmp->link=copy->link; 
     copy->link=tmp; 
    } 
    current=current->link; 
} 
while(current1!=NULL){ 
    copy=merge; 
    while(copy->link!=NULL) 
     copy=copy->link; 
    node *tmp; 
    tmp=(node*)malloc(sizeof(node)); 
    tmp->data=current1->data; 
    tmp->link=copy->link; 
    copy->link=tmp; 
    current1=current1->link; 
} 
display(merge); 

}