Найти общие узлы из двух связанных списков с помощью рекурсии

Question

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

Например,

первый список 2 -> 5 -> 7 -> 10

второй список 2 -> 4 -> 8 -> 10

списка, который будет возвращается 2 -> 10

Я никуда не могу с этим .. То, что я думал, было проверить каждое значение первого списка с каждым значением второго списка рекурсивно, но второй список затем будет разрезан один узел каждый раз, и я не могу сравнивать следующее значение в первом списке с th e второй список. Надеюсь, это имеет смысл ...

Может ли кто-нибудь помочь?

Answer 1

Эта проблема зависит от ограничений.

Простейшее, наивное решение, если у вас есть два элемента размером n, вы перебираете один список и сравниваете его со всеми элементами во втором списке.

Решение O (п)

Но, конечно, вы можете сделать гораздо лучше.

Теперь, если у вас есть HashSet (или другой около-O (1)) структуру данных доступной, то это то, что вы можете сделать:

перебирать один список. Добавьте каждый элемент в набор. Перейдите во второй список. Если элемент находится в наборе, добавьте его в список результатов.

Решение O (п)

Answer 2

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

Node merge(Node n1, Node n2) { 
    IF n1 == null OR n2 == null 
     RETURN null 
    ELSE IF n1.value == n2.value 
     Node dupNode(n1.value); 
     dupNode.next = merge(n1.next, n2.next); 
     RETURN dupNode; 
    ELSE IF n1.value < n2.value 
     RETURN merge(n1.next, n2) 
    ELSE 
     RETURN merge(n1, n2.next) 
} 

Учитывая список длины L1 и L2, это будет объединить их в O(L1 + L2). Он делает это без разрушения, создавая новые узлы для дубликатов. Вы можете легко изменить его, чтобы «украсть» из одного из списков, если хотите.

Answer 3

Если вам не нужны дубликаты с использованием встроенного метода keepAll() Set, это простое решение.

List<T> list1 = ...; // The smaller list 
    List<T> list2 = ...; 

    ... 
    final Set<T> s1 = new HashSet<T>(list1); 
    s1.retainAll(list2); 
    // Try s1.retainAll(new HashSet<T>(list2)); if the lists are really bug 

    final List<T> solution = new LinkedList(s1); 

Answer 4

Существует много способов интерпретировать вопрос. Мы ищем пересечение множеств, представленных списками, или мы ищем самую длинную общую подпоследовательность? списки всегда отсортированы?

В моем рекурсивном решении, я полагаю, что мы ищем какую-то длинной подпоследовательности, и я ничего о деталях не предполагаю заказ:

private static <T> List<T> longestCommonSubseq(List<T> a, int indA, List<T> b, int indB){ 
    if (indA == a.size() || indB == b.size()) 
     return Collections.emptyList(); 

    T itemA = a.get(indA); 
    T itemB = b.get(indB); 

    List<T> res; 
    if (itemA.equals(itemB)){ 
     res = new ArrayList<T>(); 
     res.add(itemA); 
     res.addAll(longestCommonSubseq(a, indA+1, b, indB+1)); 
    }else{ 
     List<T> opt1 = longestCommonSubseq(a, indA+1, b, indB); 
     List<T> opt2 = longestCommonSubseq(a, indA, b, indB+1); 
     if (opt1.size()>opt2.size()) 
      res = opt1; 
     else 
      res = opt2; 
    } 
    return res; 
} 

public static <T> List<T> longestCommonSubseq(List<T> a, List<T> b){ 
    return longestCommonSubseq(a,0,b,0); 
} 

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

Answer 5

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

Обратите внимание, что хотя это хвостовое рекурсивно, Java (как правило) не оптимизирует это, так что это приведет к удалению стека для длинных списков.

import java.util.*; 

    public class CommonNodeLinkedList { 
     public static void main(String[] args) { 
      List<Integer> list1_items = Arrays.asList(2, 5, 7, 10); 
      List<Integer> list2_items = Arrays.asList(2, 4, 8, 10); 

      LinkedList<Integer> list1 = new LinkedList<Integer>(); 
      list1.addAll(list1_items); 
      LinkedList<Integer> list2 = new LinkedList<Integer>(); 
      list2.addAll(list2_items); 

      System.out.println("List 1  : " + list1); 
      System.out.println("List 2  : " + list2); 
      System.out.println("Common Nodes: " + findCommonNodes(list1, list2)); 
     } 

     public static LinkedList<Integer> findCommonNodes(LinkedList<Integer> list1, 
LinkedList<Integer> list2) { 
      return findCommonNodes_helper(list1, list2, new LinkedList<Integer>()); 
     } 

     public static LinkedList<Integer> findCommonNodes_helper(LinkedList<Integer> list1, 
LinkedList<Integer> list2, 
LinkedList<Integer> result) { 
      if (list1.isEmpty()) return result; 
      Integer head = list1.pop(); 
      if (list2.contains(head)) { 
       result.add(head); 
      } 
      return findCommonNodes_helper(list1, list2, result); 
     } 

    } 

Answer 6

Есть два список ссылок, как показано ниже:

1 ---> 2 ---> 3 ---> 4 ---> 5 ---> 6 ---> 7 ---> 8

---> Ь ---> с ---> 5 ---> 6 ---> 7 ---> 8

Затем нам нужно выяснить, объединяющий узел.

Algo:

1. Вычислить длину первого списка Link, позволяет сказать, что это "len1".
2. Рассчитайте длину второго списка ссылок, скажем, это «len2».
3. Узнайте больше длины len1 и len2. в данном примере len1> len2.
4. Узнайте о положительном различии len1 и len2 в данном примере | len1 - len2 |
5. Теперь возьмите 1 указатель (ptr1) в большом списке ссылок и поместите его на len1 - len2 | с самого начала.
6. Возьмите 1 указатель (ptr2) и поместите его в начало списка ссылок.
7. увеличивайте оба указателя один за другим и проверяйте их, если они встречаются, то есть точка слияния двух списков ссылок.

Algo с данным примером: 1. len1 = 8 2. len2 = 7 3. len1> len2 4. | len1 - len2 | = 1 5. ptr1 = 2 узла первого списка ссылок 6. ptr2 = 1 узел второго списка ссылок 7. в списке ссылок1, 3rd -> next и c -> next в списке ссылок2 будет указывать на то же самое узел, который является 4-м узлом, поэтому он является объединяющим узлом.

Answer 7

Если связанный список уже отсортирован, чем вы можете очень эффективно применить рекурсию это от GeeksforGeeks

http://www.geeksforgeeks.org/intersection-of-two-sorted-linked-lists/ смотреть на 3-й вариант.

struct node *sortedIntersect(struct node *a, struct node *b) 
{ 
    /* base case */ 
    if (a == NULL || b == NULL) 
     return NULL; 

    /* If both lists are non-empty */ 

    /* advance the smaller list and call recursively */ 
    if (a->data < b->data) 
     return sortedIntersect(a->next, b); 

    if (a->data > b->data) 
     return sortedIntersect(a, b->next); 

    // Below lines are executed only when a->data == b->data 
    struct node *temp = (struct node *)malloc(sizeof(struct node)); 
    temp->data = a->data; 

    /* advance both lists and call recursively */ 
    temp->next = sortedIntersect(a->next, b->next); 
    return temp; 
}