LinkedList Intersection

Lessons Covered: Pointers, traversing, helper methods

Question 1: Given two singly LinkedListNodes, determine if the two lists intersect. Return the intersecting node. Note that the intersection is defined based on reference, not value. If the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, they are intersecting.

One immediate solution is to traverse both linked lists at the same time until you reach an intersection. For this example, we would make a pointer at nodes 2 and 7, and traverse each one-by-one until we reach a common node.

However, as you may have noticed, this will not work as the lengths of the two LinkedLists may differ. What we want to do essentially is “chop off” the beginning part of the longer LinkedListNode, and then iterate repeatedly.

Below is the method to achieve this.

We make use of helper methods here. We use getKthNode() to get the kth node of the given linked list. This is helpful when traversing the longer linked list to “chop off” extra nodes. We also use getTailAndSize() which captures both the length and the last node of the given list. This is helpful because we definitely need the size to compare lengths of the lists, and we need the tails because if the tails of the two lists are unequal, then they don’t intersect at all. Note that when we say “unequal”, we mean that the two nodes do not reference the same object. Even though they may have the same value and look identical, they must reference the same LinkedListNode to count as equal. (More information on this here). Going back to the question, if we come across the case where the tails are unequal, we return a failed value (null).

We’re done!

Coding GIF by memecandy

More Questions:

Interested in breaking into Computer Science? Eager to expand your knowledge base and learn new things? Enjoy problem solving? If so, this newsletter is for you. Subscribe to get fully explained interview prompts commonly given in engineering interviews, from Arrays to Dynamic Programming. Questions come out weekly and are also categorized by subject and difficulty.

Subscribe to get full access to the newsletter. Never miss an update.