java - 两个单链表的非破坏性递归相交

Question

我想获取两个单向链表(此函数从一个内部调用)并创建第三个单向链表，其中包含两者之间的所有交集。所以如果 p=[0,1,2,3] 和 q=[1,3,7,9] 那么 out=[1,3]，同时保持旧列表不变。

如您所见，我需要在两个地方声明“out”。但是如果我通过再次调用函数来点击声明，它自然会删除我之前写入的内容。我真的不知道如何避免它。

单链表可以用http://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html生成.首先是我的标题。

public List intersection(List l) {
    if(first.data == l.first.data) {
        List lTail = new List(l.first.next);
        List tail = new List(first.next);

        List out = new List(new Node(first.data, null)); //Bad idea #1
        // System.out.println(out);

        return tail.intersection(lTail);
    } else if (first.data > l.first.data && l.first.next != null) {
        List lTail = new List(l.first.next);
        return intersection(lTail);

    } else if (first.data < l.first.data && first.next != null) {
        List tail = new List(first.next);
        return tail.intersection(l);
    } else { //When both lists are at the end position
        List out = new List(new Node(0, null)); // Bad idea #2
        return out;
    }
}

Answer 1

List<T> p = new LinkedList<T>();
p.add...
...
List<T> q = new LinkedList<T>();
q.add...
...
List<T> intersection = new LinkedList<T>(p);
intersection.retainAll(q);

现在 intersection 只包含两个列表中的元素，而列表本身保持不变。