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

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/看看第三个选项。

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

如果您不关心重复项，那么使用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);