Check if two singly-linked lists intersect

Question: given two singly linked lists, determine if they intersect one another without modifying them.

Understand the question: first of all, we need to understand what intersecting linked lists are. Let's say we have two linked lists 1->2->3->4->5 and 10->20->30->5, they intersect each other because each list passes through the node 5. It's hard to visualize it in our head, so here is the picture:

Solution: to know whether two lists intersect, we just have to check if they share any common node. This is easy to be done with two pointers. One starts at the head of one list while the other starts at the head of the other list. Those pointers will run till the end of their lists or till they meet (pointing to the same node). If they meet, the two linked lists intersect. But if one pointer reaches the end of its list and hasn't met the other pointer yet, then the two linked lists do not intersect.

However, there is a small problem with our approach. When the lists have different lengths such as the ones in our example, the two pointers may never meet even if the lists intersect. Thus, we need to take into account that situation.

One way to solve that problem is to find out the lengths of the list. If they have different lengths, we'll calculate the difference in number of nodes between the shorter list and the longer list. Then, we'll move the pointer of the longer list ahead by that many nodes before starting to check for intersection. Our pointers are guaranteed to meet if there is intersection. Here is the implementation in Java:

private static boolean areListsIntersected(Node list1, Node list2)
{
    if (list1 == null || list2 == null)
      return false;

    if (list1 == list2)
      return true;

    int list1Len = 0;
    Node it1 = list1;
    while (it1 != null)
    {
      list1Len++;
      it1 = it1.next;
    }

    int list2Len = 0;
    Node it2 = list2;
    while (it2 != null)
    {
      list2Len++;
      it2 = it2.next;
    }

    int lenDiff = 0;
    it2 = list2;
    it1 = list1;

    if (list2Len > list1Len)
    {
      lenDiff = list2Len - list1Len;
      
      while (lenDiff > 0)
      {
        it2 = it2.next;
        lenDiff--;
      }
    }
    else if (list1Len > list2Len)
    {
      lenDiff = list1Len - list2Len;
      while (lenDiff > 0)
      {
        it1 = it1.next;
        lenDiff--;
      }
    }

    while (it2 != null && it1 != null)
    {
      if (it2 == it1)
        return true;
      it1 = it1.next;
      it2 = it2.next;
    }

    return false;
}

Explanation: our method takes two lists as arguments. It returns true if those lists intersect and false if they don't. The first two if statements are used to check for null lists and special case where the head of one list is the end node of the other list. When there are no null or special lists, we do the following:

1. First while loop counts the number of nodes in the first list.
2. Second while loop counts the number of nodes in the second list.
3. After having the length of each list, we find the difference in number of nodes and then move whichever pointer that points to the longer list ahead using that difference.
4. Finally, the while loop is used to find the intersection. We just loop until either of the pointers reaches the end of its list. During the loop, if the pointers meet, we return true immediately because it means that the lists intersect. But at the end of the loop and nothing has happened, we simply return false because the lists don't intersect.

You may notice that the pointers will meet at the first node that both lists share! Thus, this algorithm can be tweaked a little bit to return the intersection node of two intersecting lists. Or, this algorithm can be used to break two intersecting lists at their intersection node. Pretty neat huh?

Anyway, time complexity is O(m + n) where m and n are the number of nodes in the first and second list respectively. The space complexity is O(1).

Thanks for reading and until next time.