Jobs

Interviews

Discussions

Intersection of Two Linked Lists

Easy

Amazon

4 views

Topics:

Linked ListsTwo Pointers

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.

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

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

      4 -> 1 -> 8 -> 4 -> 5
5 -> 6 -> 1 -> 8 -> 4 -> 5

In the example above, the lists intersect at the node with value 8.

Example 1:

Input: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
Output: Node with value 8

Example 2:

Input: listA = [1,9,1,2,4], listB = [3,2,4]
Output: Node with value 2

Example 3:

Input: listA = [2,6,4], listB = [1,5]
Output: null

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

Intersection of Two Linked Lists

Easy

Amazon

4 views

Topics:

Linked ListsTwo Pointers

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.

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

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

      4 -> 1 -> 8 -> 4 -> 5
5 -> 6 -> 1 -> 8 -> 4 -> 5

In the example above, the lists intersect at the node with value 8.

Example 1:

Input: listA = [4,1,8,4,5], listB = [5,6,1,8,4,5]
Output: Node with value 8

Example 2:

Input: listA = [1,9,1,2,4], listB = [3,2,4]
Output: Node with value 2

Example 3:

Input: listA = [2,6,4], listB = [1,5]
Output: null

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked lists contain cycles?
Are the linked lists guaranteed to be non-empty?
If the lists intersect, is it possible for them to intersect at multiple points?
Are the values within the nodes of the linked lists unique, or can they contain duplicates?
By 'intersect', do you mean they share the exact same node object in memory, or simply have nodes with equal values at some point?

Brute Force Solution

Approach

We want to find where two lists connect, like two roads merging into one. The most straightforward way is to check every possible pair of locations from the two lists to see if they are the same point. This approach is like comparing each item in one list against every item in the other list until we find a match.

Here's how the algorithm would work step-by-step:

Start with the very first item of the first list.
Then, go through every single item in the second list and see if any of them is the exact same as the item you picked from the first list.
If you find a match, you've found the intersection point, and you are done.
If you don't find a match after checking every item in the second list, move on to the second item in the first list.
Repeat the process of comparing this second item from the first list with every item in the second list.
Keep repeating this process of picking an item from the first list and comparing it to every item in the second list until you either find a match or you run out of items in the first list.

Code Implementation

def get_intersection_node_brute_force(head_a, head_b):
    current_node_list_a = head_a

    # Iterate through each node in the first linked list
    while current_node_list_a:
        current_node_list_b = head_b

        # Compare the current node from the first list
        # with every node in the second list
        while current_node_list_b:

            # Check if the current nodes are the same node
            if current_node_list_a == current_node_list_b:
                # If the nodes are the same, we've found the intersection
                return current_node_list_a

            current_node_list_b = current_node_list_b.next

        # Move to the next node in the first list
        current_node_list_a = current_node_list_a.next

    # If there is no intersection, return None
    return None

Big(O) Analysis

Time Complexity

O(mn) – The algorithm iterates through each of the 'm' nodes in the first linked list. For each of these 'm' nodes, it iterates through all 'n' nodes in the second linked list to check for a matching node (intersection). Therefore, for every node in the first list, we perform 'n' comparisons. This leads to a total of m * n comparisons. Thus, the time complexity is O(mn).

Space Complexity

O(1) – The provided algorithm iterates through the two linked lists using only a few pointer variables to track the current nodes being compared. It doesn't create any auxiliary data structures like arrays, hash maps, or additional lists to store intermediate results or visited nodes. The space required for these pointer variables remains constant irrespective of the lengths of the linked lists, denoted as N. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The key insight is that if two lists intersect, their tails will be identical. We first figure out how much longer one list is than the other. Then, we advance the pointer of the longer list by the difference in lengths so both pointers are equidistant from the potential intersection point.

Here's how the algorithm would work step-by-step:

First, walk through each linked list to find out how long each one is.
Figure out which list is longer and by how much.
Move the pointer of the longer list forward by the difference in lengths. This way, both pointers will be the same distance from the end of their respective lists.
Now, move both pointers forward one step at a time, comparing the nodes they point to.
If the pointers ever point to the exact same node, that's where the lists intersect! Return that node.
If you reach the end of both lists without finding a matching node, it means they don't intersect at all. Return nothing in this case.

Code Implementation

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def get_intersection_node(head_a, head_b):
    list_a_length = 0
    list_b_length = 0
    current_node_a = head_a
    current_node_b = head_b

    while current_node_a:
        list_a_length += 1
        current_node_a = current_node_a.next

    while current_node_b:
        list_b_length += 1
        current_node_b = current_node_b.next

    current_node_a = head_a
    current_node_b = head_b

    # Advance the pointer of the longer list
    if list_a_length > list_b_length:
        length_difference = list_a_length - list_b_length
        for _ in range(length_difference):
            current_node_a = current_node_a.next
    elif list_b_length > list_a_length:
        length_difference = list_b_length - list_a_length
        for _ in range(length_difference):
            current_node_b = current_node_b.next

    # Move both pointers until they meet or reach the end
    while current_node_a and current_node_b:
        # Comparing the actual node objects, not just values
        if current_node_a == current_node_b:
            return current_node_a

        current_node_a = current_node_a.next
        current_node_b = current_node_b.next

    return None

Big(O) Analysis

Time Complexity

O(n) – The algorithm first iterates through both linked lists to determine their lengths. This takes O(n) time, where n is the combined length of both lists. Then, it advances the pointer of the longer list, which takes at most O(n) time. Finally, it iterates through both lists simultaneously, comparing nodes until either an intersection is found or the end of the lists is reached, which again takes at most O(n) time. Therefore, the overall time complexity is O(n) + O(n) + O(n) which simplifies to O(n).

Space Complexity

O(1) – The algorithm uses a constant amount of extra space. It stores a few pointer variables to traverse the linked lists and a couple of integer variables to hold the lengths of the lists and their difference. The space used by these variables does not depend on the size of the linked lists, N. Therefore, the auxiliary space complexity is O(1).

Edge Cases

Case	How to Handle
Both linked lists are null	Return null immediately as there can be no intersection.
One linked list is null, the other is not	Return null immediately as there can be no intersection.
Both lists are single nodes and they are the same node	Return that single node as it's the intersection.
Both lists are single nodes and they are different nodes	Return null as there is no intersection.
The lists intersect at the first node of both lists (same list)	The algorithm should correctly identify the head as the intersection point.
The lists do not intersect at all	The algorithm should correctly identify that there is no intersection and return null.
One list is significantly longer than the other	The pointer manipulation approach ensures that differing lengths are accounted for by aligning the tails.
Lists are very long, approaching memory limits	The solution should perform efficiently without creating excessive copies or auxiliary data structures, minimizing memory usage.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the linked lists contain cycles?
Are the linked lists guaranteed to be non-empty?
If the lists intersect, is it possible for them to intersect at multiple points?
Are the values within the nodes of the linked lists unique, or can they contain duplicates?
By 'intersect', do you mean they share the exact same node object in memory, or simply have nodes with equal values at some point?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the very first item of the first list.
Then, go through every single item in the second list and see if any of them is the exact same as the item you picked from the first list.
If you find a match, you've found the intersection point, and you are done.
If you don't find a match after checking every item in the second list, move on to the second item in the first list.
Repeat the process of comparing this second item from the first list with every item in the second list.
Keep repeating this process of picking an item from the first list and comparing it to every item in the second list until you either find a match or you run out of items in the first list.

Code Implementation

def get_intersection_node_brute_force(head_a, head_b):
    current_node_list_a = head_a

    # Iterate through each node in the first linked list
    while current_node_list_a:
        current_node_list_b = head_b

        # Compare the current node from the first list
        # with every node in the second list
        while current_node_list_b:

            # Check if the current nodes are the same node
            if current_node_list_a == current_node_list_b:
                # If the nodes are the same, we've found the intersection
                return current_node_list_a

            current_node_list_b = current_node_list_b.next

        # Move to the next node in the first list
        current_node_list_a = current_node_list_a.next

    # If there is no intersection, return None
    return None

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

First, walk through each linked list to find out how long each one is.
Figure out which list is longer and by how much.
Move the pointer of the longer list forward by the difference in lengths. This way, both pointers will be the same distance from the end of their respective lists.
Now, move both pointers forward one step at a time, comparing the nodes they point to.
If the pointers ever point to the exact same node, that's where the lists intersect! Return that node.
If you reach the end of both lists without finding a matching node, it means they don't intersect at all. Return nothing in this case.

Code Implementation

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def get_intersection_node(head_a, head_b):
    list_a_length = 0
    list_b_length = 0
    current_node_a = head_a
    current_node_b = head_b

    while current_node_a:
        list_a_length += 1
        current_node_a = current_node_a.next

    while current_node_b:
        list_b_length += 1
        current_node_b = current_node_b.next

    current_node_a = head_a
    current_node_b = head_b

    # Advance the pointer of the longer list
    if list_a_length > list_b_length:
        length_difference = list_a_length - list_b_length
        for _ in range(length_difference):
            current_node_a = current_node_a.next
    elif list_b_length > list_a_length:
        length_difference = list_b_length - list_a_length
        for _ in range(length_difference):
            current_node_b = current_node_b.next

    # Move both pointers until they meet or reach the end
    while current_node_a and current_node_b:
        # Comparing the actual node objects, not just values
        if current_node_a == current_node_b:
            return current_node_a

        current_node_a = current_node_a.next
        current_node_b = current_node_b.next

    return None

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Both linked lists are null	Return null immediately as there can be no intersection.
One linked list is null, the other is not	Return null immediately as there can be no intersection.
Both lists are single nodes and they are the same node	Return that single node as it's the intersection.
Both lists are single nodes and they are different nodes	Return null as there is no intersection.
The lists intersect at the first node of both lists (same list)	The algorithm should correctly identify the head as the intersection point.
The lists do not intersect at all	The algorithm should correctly identify that there is no intersection and return null.
One list is significantly longer than the other	The pointer manipulation approach ensures that differing lengths are accounted for by aligning the tails.
Lists are very long, approaching memory limits	The solution should perform efficiently without creating excessive copies or auxiliary data structures, minimizing memory usage.