找到共同的节点使用递归两个链接列表 [英] Find common nodes from two linked lists using recursion

问题描述

我必须写，返回一个链表与所有常见使用递归两个链接列表中的节点，无环路的方法。

I have to write a method that returns a linked list with all the nodes that are common to two linked lists using recursion, without loops.

例如，

第一清单中的2 - > 5 - > 7 - > 10

first list is 2 -> 5 -> 7 -> 10

第二个名单是2 - > 4 - > 8 - > 10

second list is 2 -> 4 -> 8 -> 10

这将返回的列表是2 - > 10

the list that would be returned is 2 -> 10

我一事无成这个..我一直在思考的是，与第二列表中的每个值递归，但第二个列表检查的第一个列表中的每个值，然后将一个节点，每次切，我不能比较在第一列表与所述第二列表中的下一个值。我希望这是有道理的......

I am getting nowhere with this.. What I have been think of was to check each value of the first list with each value of the second list recursively but the second list would then be cut by one node everytime and I cannot compare the next value in the first list with the the second list. I hope this makes sense...

谁能帮助？

推荐答案

这个问题只有重量，如果在每个列表中的值进行排序。如果是这样的话，那么这将找到重复的递归（伪code）

This question only has weight in it if the values in each list are sorted. If that's the case, then this will find duplicates recursively (in pseudocode)

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 ，这将在将它们合并Ø （L1 + L2）。它这样做非破坏性，通过创建重复的新的节点。您可以轻松地修改它从列表中的一个偷如果你想。

Given a list of length L1 and L2, this will merge them in O(L1 + L2). It does so non-destructively, by creating new nodes for the duplicates. You can easily modify it to "steal" from one of the lists if you wish.

这篇关于找到共同的节点使用递归两个链接列表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！