使用递归从两个链表中查找公共节点

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

这个问题取决于约束条件。

最简单、最幼稚的解决方案是，如果您有两个大小为 n 的元素，则迭代一个列表并将其与第二个列表中的每个项目进行比较。

解决方案：O(n²)

但当然你可以做得更好。

现在，如果您有一个可用的 HashSet （或其他接近 O(1)）的数据结构，那么您可以执行以下操作：

迭代一个列表。将每个元素添加到集合中。迭代第二个列表。如果该元素在集合中，则将其添加到结果列表中。

解：O(n)

Answer 3

如果链表已经排序，那么您可以非常有效地应用递归
这是来自 GeeksforGeeks

http://www.geeksforgeeks.org/intersection-两个排序链接列表/
看第三个选项。

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 4

如果您不关心重复项，那么使用 Set 的内置 keepAll() 方法是一个简单的解决方案。

  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 5

有很多方法可以解释这个问题。我们是在寻找列表表示的集合的交集，还是在寻找最长的公共子序列？列表总是排序的吗？

在我的递归解决方案中，我假设我们正在寻找一些最长的子序列，并且我不假设有关项目顺序的任何内容：

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 6

好吧，除了你的要求之外，我不会对你想要的做任何假设。下面是一个递归函数，它查找两个链表的公共元素。这需要 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 7

有两个链接列表如下：

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

a--->b--->c--->5--->6--->7--->8

然后我们需要找出合并节点。

算法：

1. 计算第一个链接列表的长度，假设它是“len1”。
2. 计算第二个链接列表的长度，假设它是“len2”。
3. 找出 len1 和 len2 中较大的长度。在给定的示例中 len1 >长度2。
4. 找出 len1 和 len2 的正差，在给定示例 |len1 - len2| 中
5. 现在在大链接列表上取出 1 个指针 (ptr1)，并将其放在 |len1 - len2| 上。从一开始的位置。
6. 取1个指针（ptr2），放在链表2的开头，
7. 将两个指针一一增加，并检查它们，如果相遇则为两个链表的合并点。

给定示例的算法：
1. 长度1=8
2. 长度2 = 7
3. len1>长度2
4.| len1 - len2 | = 1
5. ptr1 = 2 第一个链表的节点
6. ptr2 = 第二个链表的1个节点
7. 在链表1中，链表2中的3rd-->next和c-->next将指向同一个节点，即第4个节点，因此它是合并节点。