Intersection of Two Linked Lists LeetCode

Key takeaways:
Given the heads of two singly linked lists, return the node where the two lists intersect. If no intersection exists, return null.
The constraints are as follows:
List A and B have 1 to 1000 nodes each.
Each node in both lists has distinct values.
At most one node is common between the two lists.
In the brute force approach compare every node of listA with every node of listB, which is inefficient with a time complexity of $O(N * M)$ , where N and M are the lengths of the two lists.
In the optimized approach (Two-Pointer Technique):
Use two pointers, pA for listA and pB for listB.
Traverse the lists. When either pointer reaches the end of a list, switch it to the head of the other list.
If the lists intersect, the pointers will meet at the intersection node. If not, they will both reach the end (null).
The time complexity is $O(N + M),$ where $N$ is the length of listA and $M$ is the length of listB.
The space complexity is $O(1)$ , as the solution only uses constant extra space for two pointers.

Detecting an intersection point between two linked lists is a common problem in coding interviews, as it tests one’s understanding of linked list traversal and manipulation. For example, consider two linked lists: List A: 1 -> 2 -> 3 -> 4 -> 5 and List B: 9 -> 4 -> 5

The intersection occurs at node 4.

Understanding this problem is crucial because linked lists are foundational data structures in computer science. A clear comprehension can help in tackling more complex problems involving linked lists. Below is a diagram to illustrate the intersection:

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.

Constraints:

The number of nodes of headA is in the range [1, 1000].
The number of nodes of headB is in the range [1, 1000].
Each node i in headA and headB has distinct values.
The nodes of headA precede the nodes of headB in the merged list.
It is guaranteed that there is at most one node that appears in both lists.

Now, let’s look at some examples to better understand this problem:

Algorithm

The brute force approach for finding the intersection of two linked lists involves comparing each node of the first list with every node of the second list until a common node is found. However, this method is highly inefficient with a time complexity of $O(N * M)$ , where $N$ and $M$ are the lengths of the two lists.

A more efficient approach is to solve this problem using the two-pointer technique. This method aligns the pointers to ensure both traverse equal distances when checking for intersections. By initially calculating the lengths of both linked lists, we can align the starting points of the longer list such that both pointers have the same number of nodes to traverse. This synchronization ensures that when the pointers traverse together, they either meet at the intersection node or both reach the end without an intersection, thus providing an optimized solution.
Now, let’s look at the steps of this algorithm:

Initialize pA to headA and pB to headB.
While pA and pB are not pointing at the same node:
1. If pA reaches the end of list A, set pA to headB; otherwise, move pA to pA.next.
2. If pB reaches the end of list B, set pB to headA; otherwise, move pB to pB.next.
If both pointers point to the same node, return that node. Otherwise, return null if no intersection exists.

main.py

linked_list.py

list_node.py

from list_node import ListNode
from linked_list import LinkedList
def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    # Check if either of the input lists is empty.
    if not headA or not headB:
        return None
    # Initialize two pointers, pA and pB, to the heads of the input lists.
    pA, pB = headA, headB
    
    # Iterate until the pointers pA and pB point to the same node
    # or until both reach the end of their respective lists.
    while pA != pB:
        pA = pA.next if pA else headB
        pB = pB.next if pB else headA
    return pA
# Driver code with test cases
def main():
    # Test case 1: Intersection at node with value 4
    headA1 = LinkedList.create_linked_list([1, 2, 3, 4, 5])
    headB1 = ListNode(9)
    headB1.next = headA1.next.next.next
    intersection1 = getIntersectionNode(headA1, headB1)
    print("Test Case 1: Intersection at node with value", intersection1.val if intersection1 else "None")
    # Test case 2: No intersection
    headA2 = LinkedList.create_linked_list([1, 2, 3])
    headB2 = LinkedList.create_linked_list([4, 5, 6])
    intersection2 = getIntersectionNode(headA2, headB2)
    print("Test Case 2: Intersection at node with value", intersection2.val if intersection2 else "None")
    # Test case 3: Intersection at node with value 9
    headA3 = LinkedList.create_linked_list([7, 8, 9, 10])
    headB3 = LinkedList.create_linked_list([3, 4, 5])
    headB3.next.next.next = headA3.next.next
    intersection3 = getIntersectionNode(headA3, headB3)
    print("Test Case 3: Intersection at node with value", intersection3.val if intersection3 else "None")
    # Test case 4: Intersection at node with value 13
    headA4 = LinkedList.create_linked_list([11, 12, 13, 14, 15, 16])
    headB4 = LinkedList.create_linked_list([20, 21, 22])
    headB4.next.next.next = headA4.next.next
    intersection4 = getIntersectionNode(headA4, headB4)
    print("Test Case 4: Intersection at node with value", intersection4.val if intersection4 else "None")
    # Test case 5: No intersection (different lengths)
    headA5 = LinkedList.create_linked_list([1, 3, 5, 7])
    headB5 = LinkedList.create_linked_list([2, 4, 6, 8, 10])
    intersection5 = getIntersectionNode(headA5, headB5)
    print("Test Case 5: Intersection at node with value", intersection5.val if intersection5 else "None")
if __name__ == "__main__":
    main()

Intersection of Two Linked Lists in Python

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources

Intersection of Two Linked Lists LeetCode

Problem statement

Knowledge test

Algorithm

Coding example

Time complexity

Space complexity