Пересечение двух связанных списков

Question

Данные двух отсортированных связанных списков, L1 и L2, решение для вычисления их перекрестка L1 пересечение L2.

Answer 1

L1_node = L1.head; 
L2_node = L2.head; 
Result = new SList; 
while L1_node != NULL and L2_node != NULL: 
    if L1_node.value == L2_node.value: 
    Result.append(L1_node.value) 
    L1_node = L1_node.next 
    L2_node = L2_node.next 
    elif L1_node.value < L2_node.value: 
    L1_node = L1_node.next 
    else 
    L2_node = L2_node.next 

(. Перевести на C себя)

Answer 2

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

В этом случае, я хотел бы использовать ...

loop forever 
    while in1.value < in2.value : transfer item from in1 to output 
    while in2.value < in1.value : transfer item from in2 to output 

    if in1.value == in2.value : 
    transfer item from in1 to output 
    discard item from in2 

    while in1.value == value just transferred : disard item from in1 
    while in2.value == value just transferred : disard item from in2 

Теперь гадкое - это цикл предполагает, что списки бесконечны. Как вы обрабатываете пустые списки? Это неудобно, если вы не можете зарезервировать sentinel value, который больше, чем любое юридическое значение, которое может иметь место в списке.

Если вы не можете зарезервировать дозорный сигнал, вы можете подделать эффект - напишите функцию сравнения, которая проверяет, есть ли следующий элемент в каждой очереди перед сравнением значений и обрабатывает «очередь израсходована» как подразумевающая значение дозорного.

Это дает ...

loop forever 
    while in1.value < in2.value : discard item from in1 
    while in2.value < in1.value : discard item from in2 

    if in1 exhausted, break out of loop 
    if in2 exhausted, break out of loop 

    if in1.value == in2.value : 
    transfer item from in1 to output 
    discard item from in2 

    while in1.value == value just transferred : discard item from in1 
    while in2.value == value just transferred : discard item from in2 

OOPS

Это объединение. Преобразование в пересечение оставлено как упражнение для читателя.

EDIT

OK - теперь это пересечение. Просто отбрасывая меньше, чем элементы, а не добавляя их к выходу. Также исправлена ​​опечатка.

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

Answer 3

Как насчет решения ниже, это O (n + m) и принимает фиктивный узел, который указывает на узел головы. Узел Head - это переменная уровня класса, поэтому даже если L1 указывает на текущий, Head всегда имеет полный список.

Я составил и проверены, работает нормально для простых входов, как L1: 1-> 5> 6> 7> 8> 10 и L2: 2> 4> 6> 8, выход 6> 8

Любые идеи о том, как идти с несортированными списками? Я не мог думать о решении

public Node ReturnIntersection(Node Head, Node L2) { if ((Head == null) || (L2 == null)) return null;

 Node temp = null; 
     Node L1 = Head; 


     while (L1.next != null && L2.next != null) 
     { 
      if (L1.data == L2.data) 
      { 
       L1 = L1.next; 
       L2 = L2.next; 
      } 

      else if (L1.data < L2.data) 
      { 
       temp = L1.next; 
       L1.data = temp.data; 
       L1.next = temp.next; 

      } 

      else if (L1.data > L2.data) 
      { 
       L2 = L2.next; 

      } 

     } 

     if (L1 != null) 
     { 
      while (L1.next != null) 
      { 
       L1.next = null; 

      } 
     } 
     return Head; 


    } 

Answer 4

O (N) Так как они по отдельности связаны списки, если две связанные списки пересекаются они образуют форму Y с одной рукой больше или равна другой. Пусть l1 - длина списка L1, а l2 - длина списка L2.

Предположим, что l1> l2. Начните сопоставление указателей списка L1 из точки (l1-l2) и перечислите L2 с самого начала, где они указывают на тот же узел, что узел будет точкой совпадения.

Если l2 больше l1, тогда сделайте другой путь.