Intersection Of Two Linked Lists Leetcode Problem 160 [Python Solution]

In this blog post, we'll delve into solving the Intersection Of Two Linked Lists problem, which is a classic challenge on LeetCode.

We will provide an efficient Python solution that doesn't require extra memory and retains the original structure of the linked lists.

Let's start by understanding the problem, exploring its constraints, and then unveiling the solution.

Problem Overview

Question: 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.

To clarify, the linked lists must retain their original structure after the function returns.

Example 1:

Let's consider an example:

Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Intersected at '8'

In this example, the two linked lists intersect at node '8'.

The skipA and skipB values tell us how many nodes to skip to reach the intersection point in list A and list B, respectively.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'

Here, the two lists intersect at node '2'.

Again, the skipA and skipB values help us determine the exact intersection point.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection

In this case, the two lists don't intersect at all, and the expected output is 'null'.

Understanding the Constraints

Let's take a closer look at the constraints provided:

The number of nodes in listA is represented as 'm', and in listB as 'n'.
1 <= m, n <= 30,000: The linked lists can have a varying number of nodes, but they won't exceed 30,000 nodes.
1 <= Node.val <= 105: The values of the nodes in the linked lists are integers ranging from 1 to 105.
0 <= skipA < m: The number of nodes to skip in listA to reach the intersection point.
0 <= skipB < n: The number of nodes to skip in listB to reach the intersection point.
intersectVal is 0 if listA and listB do not intersect.
intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

Now that we understand the problem and its constraints, let's move on to the solution.

Intersection of Two Linked Lists LeetCode Problem Solution

Bruteforce Approach

Before we dive into the efficient solution, let's briefly discuss a bruteforce approach.

The bruteforce solution involves using extra memory, which is not an optimal solution but is good for understanding the problem.

The idea is to iterate through one of the linked lists, let's say listA, and add each node to a hash set.

Then, iterate through the other linked list, listB, checking if any of its nodes are in the hash set.

The first common node found will be the intersection point.

Here's a pseudo-code for the bruteforce approach:

def findIntersection(listA, listB):
    # Initialize a set to store nodes from listA
    nodes_set = set()
    
    # Traverse listA and add each node to the set
    current = listA
    while current:
        nodes_set.add(current)
        current = current.next
    
    # Traverse listB and check if any node is in the set
    current = listB
    while current:
        if current in nodes_set:
            return current  # Found the intersection point
        current = current.next
    
    return None  # No intersection found

This solution works but requires additional memory and is not the most efficient approach.

Now, let's move on to the more optimal approach that doesn't require extra memory.

An Efficient Approach with Two Pointers

We can solve this problem efficiently using two pointers, taking advantage of the lengths of the linked lists.

The key idea is to start two pointers at the heads of listA and listB.

We'll traverse both lists simultaneously.

If one of the pointers reaches the end of its list, we reset it to the head of the other list.

The reason this works is because if there is an intersection, the pointers will meet after eliminating the difference in the lengths of the two lists.

Here's the Python code for the efficient solution:

View on GitHub ➹

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -&gt; Optional[ListNode]:
        l1, l2 = headA, headB
        while l1 != l2:
            l1 = l1.next if l1 else headB
            l2 = l2.next if l2 else headA
        return l1

The code starts with two pointers, l1 and l2, initialized at the heads of listA and listB.

We iterate through the lists, and if either pointer reaches the end of the list, it is reset to the head of the other list.

The loop continues until l1 and l2 are equal, indicating the intersection point.

This approach has a time complexity of O(m + n), where 'm' and 'n' are the lengths of listA and listB, respectively.

It's an optimal solution in terms of time and space complexity.

Time and Space Complexity

Time Complexity: O(m + n)
- 'm' and 'n' are the lengths of listA and listB.
Space Complexity: O(1)
- This solution doesn't use any extra memory apart from a few variables.

Reasoning Behind Our Approach

The reasoning behind this approach lies in leveraging the lengths of the two linked lists.

If we imagine two runners moving at different pacesâ€”one slightly faster than the otherâ€”the faster runner will catch up with the slower runner after eliminating the difference in their starting positions.

In our solution, l1 and l2 represent the two runners.

If they have the same pace, they will meet at the intersection point.

If one runner reaches the end of its list, it is redirected to the head of the other list, which balances their starting positions.

This way, the two runners are always in sync, and they meet at the intersection point or reach the end of both lists if there's no intersection.

Conclusion

Solving the Intersection Of Two Linked Lists problem efficiently is a valuable skill for coding interviews and real-world scenarios.

By leveraging the lengths of the linked lists and using two pointers, we can find the intersection point without using extra memory

This solution has a time complexity of O(m + n), where 'm' and 'n' are the lengths of the lists, and a space complexity of O(1).

We hope this blog post has helped you understand this problem and its optimal solution.

If you have any questions, suggestions, or comments, please feel free to share them.

Your engagement and feedback are highly appreciated.

If you want to practice this problem or explore more coding challenges, you can find it on LeetCode: Intersection of Two Linked Lists.

Remember, understanding the problem-solving approach is as important as the solution itself.

Keep coding and exploring, and don't forget to like and engage to support our content.

Happy coding!