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

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).它通过为重复项创建新节点而非破坏性地完成.如果您愿意,您可以轻松地将其修改为从其中一个列表中"窃取".