如何找到一个单链表的交集

Question

我想写一个算法来找到一个单链表的交集。对于这个问题，交集节点实际上不必是相同的节点对象(即它不必是相同的内存位置)，列表只需要从交集节点到列表末尾具有完全相同的值。我写了一个非常低效的三次时间算法。我肯定有更好的，可能是递归的方法来做这个，但我不太清楚。什么好主意吗?

对于这个问题，两个列表的交集是两个列表中所有后续值完全相同的值。例如，给定:列表1 = {1,3,5,6,4,12}列表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)时间内检查两个链表中的配对元素。

(或者如果列表存储在两个向量中，可以从比较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.

不附加结构

我们可以扫描两个列表。

首先我们需要"同步"两个链表，这是O(n)，我们得到了A和b的链表深度

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

这里i = 0

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

如果它们相等，那么A'(i)是一个候选作为交集，但我们还不能确定。

向前移动A'和B，取出A'(i+1)和B(i+1)。

如果我们得到另一个相同的匹配，我们什么也不做:我们的第一个候选仍然是强的。

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

循环。

最后，我们将比反向列表方法做更多的比较，但我们将得到NULL或最近的元素，它是公共链的头。

Answer 2

1. 查找两个列表的长度- 0(n)
2. 遍历更长的列表，直到这些长度的差

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

   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;
   }
   

   }