Leetcode – Intersection of Two Linked Lists Solution in Python

Linked Lists are a fundamental data structure, and understanding how to manipulate them is essential in computer science and software development. In this detailed article, we will analyze the Intersection of Two Linked Lists problem on LeetCode, discuss different approaches to solving it, and implement these solutions using Python.

Problem Statement

The Intersection of Two Linked Lists problem is listed as problem number 160 on LeetCode. Here’s the problem statement:

Write a program to find the node at which the intersection of two singly linked lists begins.

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

A:          a1 → a2
                    ↘
                      c1 → c2 → c3
                    ↗
B:    b1 → b2 → b3

Example 1:
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8

Example 2:
Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2

Understanding the Problem

The problem entails finding the intersection point of two linked lists. The intersection point is defined as the node at which the two linked lists merge. If no such intersection point exists, we return null.

Preliminary Knowledge: Singly Linked List

A singly linked list is made up of nodes where each node has two components – data and a reference to the next node. The last node in a singly linked list points to null, signifying the end of the list.

Approach 1: Brute Force

The naive approach is to iterate through each node in the first linked list (A) and for each node, iterate through all nodes in the second linked list (B) to check if they are the same. If an intersection node is found, it is returned.

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

def getIntersectionNode(headA, headB):
    currentA = headA
    while currentA:
        currentB = headB
        while currentB:
            if currentA == currentB:
                return currentA
            currentB = currentB.next
        currentA = currentA.next
    return None

This approach has a time complexity of O(n*m) where n and m are the lengths of the linked lists. It is not the most efficient solution.

Approach 2: Using Set

Another approach is to traverse the first linked list and add each node to a set. Then, we traverse the second linked list and for each node, check if it exists in the set. The first such node is the intersection node.

def getIntersectionNode(headA, headB):
    nodes = set()
    
    currentA = headA
    while currentA:
        nodes.add(currentA)
        currentA = currentA.next
    
    currentB = headB
    while currentB:
        if currentB in nodes:
            return currentB
        currentB = currentB.next
    
    return None

This approach has a time complexity of O(n + m) but also has a space complexity of O(n) or O(m) depending on which list is longer.

Approach 3: Two Pointers

The optimal approach is to use two pointers. Initially, we have two pointers, one at the head of each linked list. We move both pointers one step at a time. When one of them reaches the end of a list, we reset it to the head of the other list. By doing this, both pointers will eventually meet at the intersection point or reach the end (if there is no intersection).

def getIntersectionNode(headA, headB):
    if not headA or not headB:
        return None
    
    pointerA = headA
    pointerB = headB
    
    while pointerA != pointerB:
        pointerA = pointerA.next if pointerA else headB
        pointerB = pointerB.next if pointerB else headA
    
    return pointerA

This approach has a time complexity of O(n + m) and a space complexity of O(1), which is the most efficient.

Conclusion

We explored three different approaches to solve the Intersection of Two Linked Lists problem on LeetCode using Python. While the brute force and set-based solutions are relatively easier to come up with, the two-pointer approach is optimal in terms of time and space complexity.

Understanding linked lists and being able to manipulate pointers are crucial skills in tackling such problems. The two-pointer approach, in particular, demonstrates a clever way to synchronize the traversal of two linked lists which may have different lengths. This technique is not only useful for this specific problem but is a powerful tool that can be employed in solving other linked list related challenges as well.