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

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

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

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

Если l2 больше, чем l1, сделайте иначе.

Answer 3

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

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

Есть идеи о том, как работать с несортированными списками? Я не мог придумать решение O (n)

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

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

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

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

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

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

Это дает ...

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

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

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