java - 两个列表的交点JAVA

Question

问题:给定两个可能相交也可能不相交的链表的头节点，判断它们是否相交并返回交点；否则返回 null。

求解时间:o(m+n)，空间o(1):

• 找出两个链表的长度:L1 和 L2
• 计算两个链表的长度差:d = |L1 - L2|
• 将较长列表“d”的头指针向前移动
• 现在遍历两个列表，比较节点直到找到匹配项或 到达列表末尾

代码如下:

public static LinkedListNode intersect(
    LinkedListNode head1,
    LinkedListNode head2) {

    LinkedListNode list1node = null;
    int list1length = get_length(head1);
    LinkedListNode list2node = null;
    int list2length = get_length(head2);

    int length_difference = 0;
    if(list1length >= list2length) {
      length_difference = list1length - list2length;
      list1node = head1;
      list2node = head2;
    } else {
      length_difference = list2length - list1length;
      list1node = head2;
      list2node = head1;
    }

    while(length_difference > 0) {
      list1node = list1node.next;
      length_difference--;
    }

    while(list1node != null) {
      if(list1node == list2node) {
        return list1node;
      }

      list1node = list1node.next;
      list2node = list2node.next;
    }
    return null;
}

但是，我在想Intersection Point 是否有可能出现在较长列表中d 步之前的位置？喜欢:

我很迷茫，请帮我理清思路，谢谢!

Answer 1

一个节点只能有一个后继者。而在第二张图中，交集节点有两个后继，这是不可能的。