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

Question

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

Например,

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

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

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

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

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

Answer 1

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

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 2

Если связанный список уже отсортирован, то вы можете очень эффективно применить рекурсию это от 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;
}

Answer 3

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

Самое простое и наивное решение: если у вас есть два элемента размером n, вы выполняете итерацию по одному списку и сравниваете его с каждым элементом во втором списке.

Решение: O (n ² )

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

Теперь, если у вас есть структура данных HashSet (или другая близкая к O (1)), то вы можете сделать следующее:

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

Решение: O (n)

Answer 4

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

* * 1 тысяча два ---> 2 ---> 3 ---> 4 ---> 5 ---> 6 ---> 7 ---> 8

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

Тогда нам нужно найти узел слияния.

Algo:

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

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

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

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

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

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 7

Если вам нет дела до дубликатов с помощью встроенного в Set метода retainAll (), это простое решение.

  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);