LeetCode 160 Intersection of Two Linked Lists in Java

In this post I will be solving LeetCode 160 Intersection of Two Linked Lists using the Java programming language.

Given the heads of two singly linked-lists headA and headB, 
return the node at which the two lists intersect. 
If the two linked lists have no intersection at all, return null.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

o intersectVal - The value of the node where the intersection occurs.
  This is 0 if there is no intersected node.
o listA - The first linked list.
o listB - The second linked list.
o skipA - The number of nodes to skip ahead in listA (starting from the head) 
  to get to the intersected node.
o skipB - The number of nodes to skip ahead in listB (starting from the head) 
  to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, 
headA and headB to your program.
If you correctly return the intersected node,
then your solution will be accepted.

Constraints:

o The number of nodes of listA is in the m.
o The number of nodes of listB is in the n.
o 1 <= m, n <= 3 * 104
o 1 <= Node.val <= 105
o 0 <= skipA < m
o 0 <= skipB < n
o intersectVal is 0 if listA and listB do not intersect.
o intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Related Topics:

* Hash Table
o Linked List
* Two Pointers

Follow up:

* Could you write a solution that runs in O(m + n) time and use only O(1) memory?

If interested I suggest you get the current description from LeetCode before you start coding.

In a nutshell we are given two singly linked lists which may or may not intersect (have a common node) and we need to find the intersection node or return `null` if they do not intersect.

It is quite interesting to me that LeetCode added data for us to help us write a test scaffold if needed. If you solve the problem using the online IDE provided by LeetCode the additional information should be of no interest. In my case I tend to develop the solution on a Windows or a Linux computer. When I feel I have code to test, I copy and paste it to the online IDE provided by LeetCode and submit it for evaluation. That said; I tend to write test code on my machine to speed up the development process. I typically use a Test Driven Development approach which requires multiple passes and displaying contents of variables. In this case the additional data, which I could have implied, helps my approach of developing a test scaffold. Thanks LeetCode!

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
    }
}

The signature for the function of interest is as expected. We are provided the head of the two linked lists in question and are asked to return the intersection node if any or `null` if the lists do not intersect.

Please go back to the problem description and read the last line. I will develop at least two approaches. The first would be a Minimum Viable Product or brute force approach while the latter would try to get to a fast O(n + m) runtime with O(1) space.

8
4,1,8,4,5
5,6,1,8,4,5
2
3
main <<< intersectVal: 8
main <<<         arrA: [4, 1, 8, 4, 5]
main <<<        skipA: 2
main <<<         arrB: [5, 6, 1, 8, 4, 5]
main <<<        skipB: 3
main <<<     headA: 4->1->8->4->5
main <<< intersect: 8
main <<<     headB: 5->6->1->8->4->5
main <<< intersect: 8
main <<< getIntersectionNode0: 8
<<< [1] p: null q: 5
<<< [2] p: 6 q: null
main <<< getIntersectionNode1: 8
<<< p: 8 q: 8
main <<<  getIntersectionNode: 8


2
1,9,1,2,4
3,2,4
3
1
main <<< intersectVal: 2
main <<<         arrA: [1, 9, 1, 2, 4]
main <<<        skipA: 3
main <<<         arrB: [3, 2, 4]
main <<<        skipB: 1
main <<<     headA: 1->9->1->2->4
main <<< intersect: 2
main <<<     headB: 3->2->4
main <<< intersect: 2
main <<< getIntersectionNode0: 2
<<< [1] p: 2 q: null
<<< [2] p: null q: 1
main <<< getIntersectionNode1: 2
<<< p: 2 q: 2
main <<<  getIntersectionNode: 2


0
2,6,4
1,5
3
2
main <<< intersectVal: 0
main <<<         arrA: [2, 6, 4]
main <<<        skipA: 3
main <<<         arrB: [1, 5]
main <<<        skipB: 2
main <<<     headA: 2->6->4
main <<< intersect: null
main <<<     headB: 1->5
main <<< intersect: null
main <<< getIntersectionNode0: null
<<< [1] p: 4 q: null
<<< [2] p: null q: 6
<<< [3] p: null q: null
main <<<  getIntersectionNode: null

Test cases are separated with two blank lines.

The first five lines in a test case are input lines. The first line holds the value for the `intersectVal` which is the value of the intersect node. The next two lines hold the values for the nodes in the first and second linked lists. The fourth line contains the value for the `skipA` and the fifth for the `skipB`. These last two values indicate the number of nodes to skip before the intersect node (if any). Please refer to the requirement section in the problem definition at the LeetCode web site. Note that the values are not provided to the function of interest. They are used by the `judge` or in our case by the test scaffold to help generate the two linked lists used as arguments for the function of interest.

The test scaffold reads the input lines, allocates and populates the necessary variables, constructs the two linked lists which will be used as arguments to the function of interest, and displays the values. This is done for us to verify that all is well before calling the function of interest.

There are three calls to three implementations of the function of interest. Some of the functions display some intermediate values which should help us understand how the algorithm operates. When done, the returned value is displayed.

    /**
     * Test scaffold.
     * 
     * !!! NOT PART OF SOLUTION !!!
     * 
     * @throws IOException
     */
    public static void main(String[] args) throws IOException {
        
        // **** initialization ****
        ListNode[] intersect = new ListNode[1];

        // **** open buffered reder ****
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        // **** read intersectVal ****
        int intersectVal = Integer.parseInt(br.readLine().trim());

        // **** read values for linked list A****
        int[] arrA = Arrays.stream(br.readLine().trim().split(","))
                        .mapToInt(Integer::parseInt)
                        .toArray();

        // **** read values for linked list A****
        int[] arrB = Arrays.stream(br.readLine().trim().split(","))
                        .mapToInt(Integer::parseInt)
                        .toArray();

        // **** read `skipA` ****
        int skipA = Integer.parseInt(br.readLine().trim());
        
        // **** read `skipB` ****
        int skipB = Integer.parseInt(br.readLine().trim());

        // **** close buffered reader ****
        br.close();
        
        // ???? ????
        System.out.println("main <<< intersectVal: " + intersectVal);
        System.out.println("main <<<         arrA: " + Arrays.toString(arrA));
        System.out.println("main <<<        skipA: " + skipA);
        System.out.println("main <<<         arrB: " + Arrays.toString(arrB));
        System.out.println("main <<<        skipB: " + skipB);

        // **** populate linked list head1 ****
        ListNode headA = populate(arrA, skipA, intersect);
        
        // ???? ????
        System.out.println("main <<<     headA: " + toString(headA));
        System.out.println("main <<< intersect: " + intersect[0]);

        // **** populate linked list head2 ****
        ListNode headB = populate(arrB, skipB, intersect);
        
        // ???? ????
        System.out.println("main <<<     headB: " + toString(headB));
        System.out.println("main <<< intersect: " + intersect[0]);

        // **** invoke function of interest and display result ****
        System.out.println("main <<< getIntersectionNode0: " + getIntersectionNode0(headA, headB));
    
        // **** invoke function of interest and display result ****
        System.out.println("main <<< getIntersectionNode1: " + getIntersectionNode1(headA, headB));

        // **** invoke function of interest and display result ****
        System.out.println("main <<<  getIntersectionNode: " + getIntersectionNode(headA, headB));
    }

The test scaffold uses a buffered reader to read the five input lines. The values are then displayed.

The linked lists are then generated using the `populate` function which IS NOT PART OF THE SOLUTION.

The contents of the linked lists are displayed by the `toString` function which IS NOT PART OF THE SOLUTION.

The test code then calls three implementations of the function of interest. The returned value is displayed.

Please note that the test scaffold IS NOT PART OF THE SOLUTION!

    /**
     * Given the heads of two singly linked-lists headA and headB,
     * return the node at which the two lists intersect.
     * If the two linked lists have no intersection at all, return null.
     * 
     * Using a hash set.
     * 
     * Runtime: O(n + m) - Space: O(n)
     * 
     * Runtime: 7 ms, faster than 26.61% of Java online submissions.
     * Memory Usage: 43.1 MB, less than 23.58% of Java online submissions.
     * 
     * 39 / 39 test cases passed.
     * Status: Accepted
     * Runtime: 7 ms
     * Memory Usage: 43.1 MB
     */
    static public ListNode getIntersectionNode0(ListNode headA, ListNode headB) {
        
        // **** sanity checks ****
        if (headA == null ||  headB == null) return null;

        // **** initialization ****
        HashSet<ListNode> hs = new HashSet<>();

        // **** traverse headA linked list populating hash set ****
        for (ListNode p = headA; p != null; p = p.next)
            hs.add(p);

        // **** traverse headB linked list ****
        for (ListNode p = headB; p != null; p = p.next)
            if (hs.contains(p)) return p;

        // **** lists do NOT intersect ****
        return null;
    }

In this implementation of the function of interest we will use a hash set to keep track of the nodes in the `headA` linked list.

The first linked list is traversed and the objects are stored in the hash set.

We then traverse the `headB` linked list. We check if a node in the second linked list is also in the first linked list. If so, we found the intersect node, and we returned it.

If the intersect node is not found it implies that the linked lists do not intersect. We need to return `null` to indicate so.

Check the comments section for this function. The solution was accepted but it does not meet the condition specified in the follow up section of the requirements. Hopefully we will do better in the next implementation which should use two pointers.

I spent some time trying some things at no avail. I then searched the web and found the article Write a function to get the intersection point of two Linked Lists. If you take a look at the article, go to the Method 8 (2-pointer technique) and read how the algorithm should be implemented.

In a nutshell we need to detect the distance between two pointers and then find the intersect node (if present).

After you read the article and figured out how it works, we can move forward and look at the second implementation of the function of interest.


    /**
     * Given the heads of two singly linked-lists headA and headB,
     * return the node at which the two lists intersect.
     * If the two linked lists have no intersection at all, return null.
     * 
     * Using two pointers.
     * 
     * Execution: O(n + m) - Space: O(1)
     * 
     * Runtime: 1 ms, faster than 97.75% of Java online submissions.
     * Memory Usage: 41.5 MB, less than 88.45% of Java online submissions.
     * 
     * 39 / 39 test cases passed.
     * Status: Accepted
     * Runtime: 1 ms
     * Memory Usage: 41.5 MB
     */
    static public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        
        // **** sanity checks ****
        if (headA == null ||  headB == null) return null;

        // **** 1. initialization ****
        ListNode p = headA;
        ListNode q = headB;

        // **** 2. traverse both lists ****
        while (p != null && q != null) {
            p = p.next;
            q = q.next;
        }

        // ???? ????
        System.out.println("<<< [1] p: " + p + " q: " + q);        

        // **** 3. one pointer reached the end of a list, redirect it to the other head ****
        if (p == null) p = headB;
        else if (q == null) q = headA;

        // **** traverse both lists ****
        while (p != null && q != null) {
            p = p.next;
            q = q.next;
        }

        // ???? ????
        System.out.println("<<< [2] p: " + p + " q: " + q);

        // **** 4. one pointer reached the end of a list, redirect it to the other head ****
        if (p == null) p = headB;
        else if (q == null) q = headA;

        // **** traverse both lists****
        while (p != null && q != null) {

            // **** 5 & 6 found intersection node ****
            if (p.equals(q)) return p;

            // **** increment both pointers ****
            p = p.next;
            q = q.next;
        }

        // ???? ????
        System.out.println("<<< [3] p: " + p + " q: " + q);

        // **** 7. lists do NOT intersect ****
        return null;
    }

In this implementation I have placed some comments with a starting sequential integer. The integers map to the steps described in the 2-pointer technique algorithm.

If you read the article and look at the code you should be able to follow the algorithm and understand how it works. Note that in the LeetCode 142 Linked List Cycle II in Java post we used a similar technique to locate the cycle node in a linked list.

Please take a look at the comments section in the function of interest. Our execution time improved and we met the follow up requirements. We should stop here, but it seems to me that perhaps cleaning up the code could produce a faster algorithm. Spoiler alert, it did very little.

   /**
     * Given the heads of two singly linked-lists headA and headB,
     * return the node at which the two lists intersect.
     * If the two linked lists have no intersection at all, return null.
     * 
     * Using two pointers (reduced code).
     * 
     * Execution: O(n + m) - Space: O(1)
     * 
     * Runtime: 1 ms, faster than 97.75% of Java online submissions.
     * Memory Usage: 41.4 MB, less than 98.04% of Java online submissions.
     * 
     * 39 / 39 test cases passed.
     * Status: Accepted
     * Runtime: 1 ms
     * Memory Usage: 41.4 MB
     */
    static public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        
        // **** sanity checks ****
        if (headA == null ||  headB == null) return null;

        // **** initialization ****
        ListNode p = headA;
        ListNode q = headB;

        // **** traverse both lists and swap pointers as needed ****
        while (p != q) {
            p = p == null ? p = headB : p.next;
            q = q == null ? q = headA : q.next;
        }

        // ???? ????
        System.out.println("<<< p: " + p + " q: " + q);        

        // **** intersection or null ****
        return p;
    }

In this implementation we have condensed the previous approach. The code is quite shorter and perhaps harder to follow and understand, but if you worked with the previous implementation this code does the same and should be somewhat faster.

Please take a look at the comments section of this implementation. The runtime remained unchanged, but saved us a little space (memory). You can debate which implementation is better. The longer code appears to be easier to debug and enhance.

    /**
     * Class for nodes in the linked list.
     */
    static class ListNode {
    
        // **** members ****
        int         val;
        ListNode    next;
    
        // **** constructor(s) ****
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    
        // **** ****
        @Override
        public String toString() {
            return "" + this.val;
        }
    }

As I was working on this post I noticed that the implementation of the ListNode class was missing. The reason I am including it is because I had to implement the class for the test scaffold.

    /**
     * Populate linked list from the contents of the specified array.
     * 
     * !!! NOT PART OF SOLUTION !!!
     */
    static ListNode populate(int[] arr, int skip, ListNode[] intersect) {
    
        // **** sanity ckeck(s) ****
        if (arr.length == 0) return null;
    
        // **** initialization ****
        ListNode head   = null;
        ListNode tail   = null;
    
        // **** traverse array inserting nodes to the linked list ****
        for (int i = 0; i < arr.length; i++) {
    
            // ???? ????
            // System.out.println("<<< arr[" + i + "]: " + arr[i]);

            // **** check if this is the intersect node (if needed) ****
            if (intersect[0] != null && i == skip) {

                // **** add this node to linked list ****
                tail.next = intersect[0];

                // **** return head of linked list ****
                return head;
            }

            // *** allocate node to insert into linked list ****
            ListNode node = new ListNode(arr[i]);

            // **** save this node (if needed) ****
            if (intersect[0] == null && i == skip)
                intersect[0] = node;

            // **** insert node into linked list ****
            if (head == null) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                tail = tail.next;
            }

            // ???? ????
            // System.out.println("<<< head: " + toString(head));
        }
    
        // **** return head of linked list ****
        return head;
    }

I did mention the `populate auxiliary function but forgot to include the source code for it. Sorry about that.

    /**
     * Generate string representation of linked list.
     * Stops after last node or cycle detected.
     * 
     * !!! NOT PART OF SOLUTION !!!
     */
    static String toString(ListNode head) {
    
        // **** sanity check(s) ****
        if (head == null) return "";
    
        // **** initialization ****
        StringBuilder sb = new StringBuilder();
    
        // **** traverse link list ****
        for (ListNode p = head; p != null; p = p.next) {
            sb.append(p.val);
            if (p.next != null)
                sb.append("->");
        }
    
        // **** return string representation of linked list ****
        return sb.toString();
    }

The `toString` function used to display the contents of linked lists by generating a string representation was also missing. We have looked at several implementations of this function with the name `display` in previous posts.

Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository named IntersectionOfTwoLinkedLists.

Please note that the code here presented might not be the best possible solution. After solving a problem, you should take a look at the best accepted solutions provided by the different websites (i.e., HackerRank, LeetCode to name a few). The idea is to learn concepts, not to memorize solutions.

If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.

Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer / engineering toolset.

Thanks for reading, feel free to connect with me John Canessa at LinkedIn.

Enjoy;

John

Leave a Reply

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.