Intersection Point of Two Lists JAVA

Question

Question: Given head nodes of two linked lists that may or may not intersect, find out if they intersect and return the point of intersection; return null otherwise.

Solution time:o(m+n),space o(1):

Find lengths of both linked lists: L1 and L2
Calculate difference in length of both linked lists: d = |L1 - L2|
Move head pointer of longer list 'd' steps forward
Now traverse both lists, comparing nodes until we find a match or reach the end of lists

Here's the code:

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

However, I'm thinking is there a possible that the Intersection Point just appear at the position before d steps in the longer list? Like:

I'm confused, please help me clear my mind, thank you!

xingbin xingbin · Accepted Answer · 2018-09-29T13:50:45

A node can only has one successor. While in the second picture, the intersection node get two successors, which is impossible.

Intersection Point of Two Lists JAVA

4 Answers