Найти узел слияния двух связанных списков?

Question

MergePoint (LinkList list1, LinkList list2){
p = list1.head;
q = list2.head;
while (p.next!=null && q.next!=null){
    if (p.next == q.next){
        System.out.print(p.value + " is the Merging node");
        return;
    }
    p=p.next;
    q=q.next;
}

}

Я пытаюсь решить проблему, чтобы найти узел слияния двух связанных списков. Прежде чем рассматривать другие решения, я решил написать свой код, а затем сравнить с другими существующими решениями. Подход, принятый здесь, заключается в том, чтобы найти общий узел, на который указывают оба указателя списка. Вы согласны с этим кодом или мне чего-то не хватает?

Answer 1

Ваш код будет работать только для специального класса случаев, когда узел слияния находится в одной и той же позиции в обоих списках. Я не думаю, что есть простой, суб-O(n^2) способ сделать это - другими словами, вам нужно сравнить каждый узел одного списка, с каждым следующим из второго списка, и наоборот.

MergePoint (LinkList list1, LinkList list2) {
    p = list1.head;
    while (p != null) {
        q = list2.head;
        while (q != null) {
            if (p == q){
                    System.out.print(p.value + " is the Merging node");
                    return;
            }
            q = q.next;
        }        
        p = p.next;
    }    
}

Answer 2

На ум приходят три решения.

Во-первых, вложенный цикл размещен Ирфием. Он использует постоянную память, но O(N*M) время, где N и M являются длинами двух списков.

Во-вторых, вы можете обменять пространство на время, сначала поместив каждый узел одного списка в HashSet, а затем пройдитесь по другому списку и выполните поиск в HashSet. Поскольку этот поиск равен O(1), общее время равно O(N+M) (создание хеш-таблицы и обход другого списка). Однако компромиссом является O(N) пространство, необходимое для таблицы.

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

Рассматриваемые алгоритмы фактически доступны в примере главы, которую вы можете скачать здесь:

http://www.elementsofprogramming.com/book.html

Answer 3

Это будет работать только в том случае, если "объединяющие узлы" находятся в одной и той же позиции в списке.

Например, допустим, у вас есть два связанных списка...

Список 2 имеет 5 узлов (узлы A, B, C, D, E). Список 2 имеет 6 узлов (узлы V, W, X, Y, C, D).

Очевидно, что общим узлом является C. То, что вы, похоже, ищете в своем коде, это узел, который указывает на общий узел (не знаю, действительно ли он имеет имя, объединяющий узел так же хорош, как и все остальное), поэтому в этом Если вы ищете A и Y.

Ваш код будет делать что-то вроде этого:

A.next == V.next? no
B.next == W.next? no
C.next == X.next? no

и так далее и тому подобное. Это в формате [Элемент из Списка 1 по сравнению с Элементом из Списка 2]

Что вы действительно хотите сделать, это сравнить первый элемент списка 1 со всеми элементами списка 2. Затем, если вы его не найдете, сравните второй элемент списка 1 со всеми элементами списка 2 и продолжайте делай так и так далее и тому подобное.

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

Также может потребоваться рассмотреть специальный случай для головного узла в случае, если первый узел в любом списке является общим узлом. В этом случае вы сравниваете только "следующий" узел, то есть самый первый из них никогда не будет совпадать, если он является общим узлом любого из двух списков.