如何找到单链表的交集

Question

我试图写一个算法来找到一个单链表的交集。对于这个问题，交集节点实际上不必是同一个节点对象(即，它不必是相同的内存位置)，列表只需要具有从交集节点到列表末尾的完全相同的值。为此，我在三次时间内编写了一个效率极低的算法。我确信有一种更好的、可能是递归的方法来实现这一点，但我无法完全弄清楚。有什么想法吗？

对于这个问题，两个列表的交集是两个列表中所有后续值都完全相同的值。例如:列表1= {1，3，5，6，4，12} list 2= {8，9，6，4，12}，算法应该返回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

我确信有一种更好的、可能是递归的方法来实现这一点，但我无法完全弄清楚。有什么想法吗？

我用O(n)时间构造一个反向列表，然后检查两个列表中的配对元素，同样是O(n)时间。

(或者，如果将列表存储在两个向量中，则可以首先将am-i和bn-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。

无附加结构

我们可以扫描两个名单。

首先，我们需要“同步”两个列表，即O(n)，然后得到A和B的列表深度。

有了这个数目，我们就按适当数目的职位提前列出较长的名单。如果A有7个元素，B有4个元素，我们就把A推进3。我们知道A的任何元素在第三条之前都不可能是一个交集，因为A的子链会比整个B长。

这里=0。

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

如果它们相等，则A'(i)是一个候选，可以作为一个交叉点，但我们还不能确定。

我们前进A‘和B，获取A'(i+1)和B(i+1)。

如果我们得到了另一场相同的比赛，我们什么也不做:我们的第一个候选人仍然很强大。

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

循环播放。

最后，我们将比反向列表方法做更多的比较，但是我们要么是NULL，要么是作为公共链的头的最新元素。

Answer 2

1. 查找两个列表的长度- 0(n)
2. 遍历较长的列表，直到这些长度的差异
3. 现在，将这两个列表放在一起，并继续比较元素值。 公共ListNode getIntersectionNode(ListNode headA，ListNode headB) { int first = 0，second = 0；if (headA == null \ headB headB == null)返回空；ListNode temp = headA；first = findLen(headA)；second = findLen(headB)；if (first > second){ return ( headA，findLen，第一-秒)；}返回(，，第二-第一)；} public (en25#，en27#，int diff){ (diff != 0){ =en29#；diff-；} while (longerList != null){ if (longerList == shorterList)返回longerList；longerList = longerList.next；shorterList = shorterList.next；}返回null；} public int findLen(ListNode a){ int len = 0；while (a != null){ len++；a= a.next；}返回len}； }