160. Intersection of Two Linked Lists

Problem Statement

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.

For example, the following two linked lists begin to intersect at node c1:

The test cases are generated such that there are no cycles anywhere in the entire linked structure.

Note that the linked lists must retain their original structure after the function returns.

Example 1:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'
Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect).

Solution

Brute force Approach

We are presented with two linked lists and our objective is to identify their common intersection point. To determine if a node is shared, we first store all nodes of one linked list in a set. Then, we traverse the second linked list, checking each node to see if it exists in the set containing nodes from the first linked list. If a match is found, we promptly return the node.

Time - O(n1+n2)

Space - O(n1) or O(n2)

/**
 * 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) {
        ListNode temp1 = headA;
        ListNode temp2 = headB;

        Set<ListNode> set = new HashSet<>();

        while(temp1!=null){
            set.add(temp1);
            temp1 = temp1.next;
        }

        while(temp2!=null){
            if(set.contains(temp2)) return temp2;
            temp2 = temp2.next;
        }

        return null;
    }
}

Better Approach

To identify the common node, we leverage the lengths of the provided linked lists. Let's denote n1 and n2 as the lengths of the given lists. If n1 is greater than n2, it indicates that n1 has a greater number of nodes compared to n2. In such a case, we initially traverse the first linked list by n1 - n2 nodes using for loop. From this point onward, we simultaneously traverse both linked lists and compare if the current nodes are equal. If they are, we return the common node; otherwise, we continue the process. Similarly, if n1 is less than n2, we adopt the same approach but begin by iterating through the second list to adjust for the disparity in lengths.

Time - O(n1) + O(n2) + O(n1-n2) + O(n2) (Assuming n1>n2)

Space - O(1)

public class Solution {

    private int lengthOfLinkedList(ListNode head){
        int length = 0;
        ListNode temp = head;

        while(temp!=null){
            length+=1;
            temp = temp.next;
        }
        return length;
    }

    private ListNode getTheCommonNode(ListNode head1, ListNode head2, int distance){
        ListNode temp1 = head1;
        ListNode temp2 = head2;

        for(int i=0; i<distance; i++){
            temp2 = temp2.next;
        }

        while(temp1!=temp2){
            temp1 = temp1.next;
            temp2 = temp2.next;
        }
        return temp1;
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode temp1 = headA;
        ListNode temp2 = headB;

        int n1 = lengthOfLinkedList(headA);
        int n2 = lengthOfLinkedList(headB);

        if(n1<n2){
            return getTheCommonNode(headA, headB, n2-n1);
        }

        return getTheCommonNode(headB, headA, n1-n2);
    }
}

Optimal Approach

This approach is exactly the same as the better approach, with the only difference being that we avoid using a for loop and instead utilize pointers to address the discrepancy. This is achieved by iteratively traversing both linked lists simultaneously. When any pointer reaches null, it will point to the first node of the opposite linked list. In the case where the linked list with the smaller length reaches null first, the other pointer will be positioned back by n1-n2 from null. Subsequently, the pointer that was pointing to null will immediately move to the other linked list and continue the iteration. At this point, there are two pointers on one linked list: one at the beginning and the other towards the end. Upon further iteration, the second pointer also reaches null, pointing to the first node of the opposite linked list. Upon visualization, both pointers are aligned at the same position, indicating that the pointer present on the larger length has already traveled a distance of n1-n2. By iterating both pointers simultaneously and checking for equality, we can identify the common node.

If there is no common node, the common intersection point will be null. Hence, before performing the null check, we compare the pointer nodes to determine if they are equal or not.

Time - O(2*max(n1,n2))

Reason - 2 because if last node is common node