如何找到单向链表的交集

Question

我正在尝试编写一种算法来查找单向链表的交集。对于这个问题，交集节点实际上不必是相同的节点对象（即它不必是相同的内存位置），列表只需要从交集节点到列表的结尾。我在立方时间内为此编写了一个非常低效的算法。我确信有更好的，可能是递归的方法来做到这一点，但我不太明白。有什么想法吗？

对于这个问题，两个列表的交集是一个值，两个列表中的所有后续值都完全相同。例如，给定：清单 1 = {1, 3, 5, 6, 4, 12} 清单 2 = {8, 9, 6, 4, 12} 算法应该return 6.

这是我当前的解决方案：我查看每个列表中的共同元素，当我找到一个时，我检查列表是否与该元素相同。

public static boolean compareFrom(Node a, Node b) {
    Node current1 = a, current2 = b;
    while (current1 != null) {
        if (current2 == null
                || !(current1.getElem().equals(current2.getElem()))) {
            return false;
        }
        current1 = current1.getNext();
        current2 = current2.getNext();
    }
    if (current2 == null)
        return true;
    return false;
}

public static Node intersection(SinglyLinkedList list1,
        SinglyLinkedList list2) {
    Node current1 = list1.head, current2 = list2.head;
    while (current1 != null) {
        while (current2 != null) {
            if (current1.getElem().equals(current2.getElem())
                    && compareFrom(current1, current2))
                return current1;
            else
                current2 = current2.getNext();
        }
        current2 = list2.head;
        current1 = current1.getNext();
    }
    return null;
}

Answer 1

I'm sure there is a better, probably recursive way to do this, but I can't quite figure it out. Any ideas?

我会在 O(n) 时间内构造一个反向列表，然后再次在 O(n) 时间内检查两个列表中的成对元素。

（或者，如果您将列表存储在两个向量中，则可以先将 a[m-i] 和 b[n-i] 与 i 从 1 到 m 和 n 之间的最小值进行比较）：

 {1, 3, 5, 6, 4, 12} and {8, 9, 6, 4, 12}
 x := -1
 a[5] = b[4] = 12 so x := 12
 a[4] = b[3] = 4 so x := 4
 a[3] = b[2] = 6 so x := 6
 a[2] != b[1] so break

交集是6.

没有额外的结构

我们可以扫描两个列表。

首先我们需要"sync"两个列表，O(n)，得到A和B的列表深度

有了这个数字，我们将较长的列表推进适当的位置数。如果我们有 7 个元素的 A 和 4 个元素的 B，我们将 A 推进三。我们知道A的第三个之前的任何元素都不可能是交集，因为A子链会比整个B长。

这里我=0。

现在我们比较 A' 的第一个可用元素，我们称它为 A'(i)，与 B 的第一个可用元素 B(i)。

如果它们相等，则 A'(i) 是候选交集，但我们还不能确定。

我们推进A'和B并获取A'(i+1)和B(i+1)。

如果我们得到另一个相同的匹配项，我们什么都不做：我们的第一个候选人仍然很强大。

如果我们没有得到一个匹配项，那么我们的候选人就不可能是有效的，我们将丢弃它，将 cand 设置为 NULL。

循环。

最后我们将进行比反向列表方法更多的比较，但我们将得到 NULL 或 作为公共链头部的最新元素。

Answer 2

查找两个列表的长度 - 0(n)
遍历较长的列表，直到这些长度的差异

现在一起遍历两个列表并继续比较元素值

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {

int first = 0, second = 0;
if (headA == null || headB == null) return null;
ListNode temp = headA;
first  = findLen(headA);
second  = findLen(headB);

if (first > second){
    return findIntersection(headA, headB, first-second);
}
return findIntersection(headB, headA, second-first);

}

public ListNode findIntersection(ListNode longerList, ListNode shorterList, int diff){

while(diff != 0){
    longerList = longerList.next;
    diff--;
}

while (longerList != null){
    if (longerList == shorterList) return longerList;
    longerList = longerList.next;
    shorterList = shorterList.next;
}
return null;
}

public int findLen(ListNode a){
int len = 0;
while (a != null){
    len++;
    a = a.next;
}
return len;
}

}

如何找到单向链表的交集

How to find the intersection of a singly linked list

algorithm

linked-list

没有额外的结构