Intersection of Two Linked Lists | Leetcode 160 | Brute, Better and Optimal Solutions

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.

Here’s the [Problem Link] to begin with.

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.

Custom Judge:

The inputs to the judge are given as follows (your program is not given these inputs):

• intersectVal – The value of the node where the intersection occurs. This is 0 if there is no intersected node.
• listA – The first linked list.
• listB – The second linked list.
• skipA – The number of nodes to skip ahead in listA (starting from the head) to get to the intersected node.
• skipB – The number of nodes to skip ahead in listB (starting from the head) to get to the intersected node.

The judge will then create the linked structure based on these inputs and pass the two heads, headA and headB to your program. If you correctly return the intersected node, then your solution will be accepted.

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).
From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,6,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
- Note that the intersected node's value is not 1 because the nodes with value 1 in A and B (2nd node in A and 3rd node in B) are different node references. In other words, they point to two different locations in memory, while the nodes with value 8 in A and B (3rd node in A and 4th node in B) point to the same location in memory.

Example 2:

Input: intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Intersected at '2'
Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect).
From the head of A, it reads as [1,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.

Example 3:

Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: No intersection
Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.

Constraints:

• The number of nodes of listA is in the m.
• The number of nodes of listB is in the n.
• 1 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• intersectVal is 0 if listA and listB do not intersect.
• intersectVal == listA[skipA] == listB[skipB] if listA and listB intersect.

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

Solution 1: Brute Force Approach (Using Set)

Intuition

Think of this like finding a common friend between two groups of people! One simple way is to write down all the names from the first group, then go through the second group and check if anyone’s name is already on your list. The first person you find who’s on both lists is your common friend. We use the same idea here – store all nodes from the first list, then check if any node from the second list is already stored.

Detailed Approach

1. Create a Storage: Use a set to store all nodes from the first linked list
2. First Pass: Walk through the first list and add every node to the set
3. Second Pass: Walk through the second list and check if each node exists in the set
4. Found Intersection: The first node from the second list that exists in the set is our intersection
5. No Intersection: If we reach the end of the second list without finding any common node, return null

Code

class Solution:
    def getIntersectionNode(
        self, headA: ListNode, headB: ListNode
    ) -> Optional[ListNode]:
        all_nodes = set()  # Set to store all nodes from first list
        temp = headA
        
        # First pass: Store all nodes from list A
        while temp:
            all_nodes.add(temp)  # Add current node to set
            temp = temp.next
        
        temp = headB
        
        # Second pass: Check each node of list B in the set
        while temp:
            if temp in all_nodes:  # Found intersection!
                return temp
            temp = temp.next
        
        return None  # No intersection found

Code Explanation

We use two separate loops here. In the first loop, we walk through the entire first linked list and store every node in a set. Sets are perfect for this because they allow fast lookups. In the second loop, we walk through the second linked list and check if each node already exists in our set. The moment we find a node that’s already in the set, we’ve found our intersection point. If we finish the second loop without finding any common nodes, the lists don’t intersect.

Dry Run

Let’s trace through two lists that intersect:

• List A: 1 -> 2 -> 8 -> 4 -> 5
• List B: 3 -> 6 -> 8 -> 4 -> 5 (they share nodes 8, 4, 5)

First Pass (Store List A nodes):

• Visit node 1: all_nodes = {1}
• Visit node 2: all_nodes = {1, 2}
• Visit node 8: all_nodes = {1, 2, 8}
• Visit node 4: all_nodes = {1, 2, 8, 4}
• Visit node 5: all_nodes = {1, 2, 8, 4, 5}

Second Pass (Check List B nodes):

• Visit node 3: 3 not in set, continue
• Visit node 6: 6 not in set, continue
• Visit node 8: 8 found in set! Return node 8

Result: Intersection at node 8

Time and Space Complexity

• Time Complexity: O(m + n) – We visit each node from both lists once
• Space Complexity: O(m) – We store all nodes from the first list in the set

Simplifying It

This approach is like keeping a guest list for a party. You write down everyone from the first group, then when people from the second group arrive, you check if their name is already on the list. The first person you recognize is your answer!

Solution 2: Better Approach (Length Calculation + Alignment)

Intuition

Imagine two people walking towards each other from different starting points on converging paths. If one person starts farther away, they need a head start to meet at the same time. Similarly, if our linked lists have different lengths, we can give the longer list a “head start” by moving its pointer forward until both lists have the same remaining length. Then we can walk both pointers together until they meet!

Detailed Approach

1. Calculate Lengths: Find the length of both linked lists and their last nodes
2. Check Possibility: If the last nodes are different, the lists don’t intersect
3. Align Starting Points: Move the pointer of the longer list forward by the difference in lengths
4. Walk Together: Move both pointers one step at a time until they meet
5. Found Intersection: When both pointers point to the same node, that’s our intersection

Code

class Solution:
    def getIntersectionNode(
        self, headA: ListNode, headB: ListNode
    ) -> Optional[ListNode]:
        lenA = 0
        lenB = 0
        lastNodeofA = None
        lastNodeofB = None
        temp = headA
        
        # Calculate length of list A and find its last node
        while temp:
            lenA += 1
            if temp.next is None:
                lastNodeofA = temp  # Store last node of A
            temp = temp.next
        
        temp = headB
        
        # Calculate length of list B and find its last node
        while temp:
            lenB += 1
            if temp.next is None:
                lastNodeofB = temp  # Store last node of B
            temp = temp.next
        
        # If last nodes are different, no intersection exists
        if lastNodeofA is not lastNodeofB:
            return None
        
        diff = abs(lenA - lenB)  # Calculate difference in lengths
        
        # Align starting points based on which list is longer
        if lenA > lenB:
            temp = headA
            # Move pointer of longer list forward by difference
            while diff > 0:
                temp = temp.next
                diff -= 1
            # Walk both pointers together until they meet
            while temp:
                if temp is headB:
                    return temp
                temp = temp.next
                headB = headB.next
        elif lenB > lenA:
            temp = headB
            # Move pointer of longer list forward by difference
            while diff > 0:
                temp = temp.next
                diff -= 1
            # Walk both pointers together until they meet
            while temp:
                if temp is headA:
                    return temp
                temp = temp.next
                headA = headA.next
        else:
            # Both lists have same length, start from beginning
            temp = headA
            while temp:
                if temp is headB:
                    return temp
                temp = temp.next
                headB = headB.next

Code Explanation

This solution works in multiple phases. First, we calculate the length of both lists while also storing their last nodes. By comparing the last nodes, we can quickly determine if the lists intersect at all – if they don’t share the same last node, they can’t intersect. If they do intersect, we calculate the difference in lengths and move the pointer of the longer list forward by that difference. This aligns both pointers so they have the same distance remaining to the intersection. Finally, we move both pointers together until they meet.

Dry Run

Let’s trace through:

• List A: 1 -> 2 -> 8 -> 4 -> 5 (length = 5)
• List B: 3 -> 6 -> 8 -> 4 -> 5 (length = 5)

Calculate Lengths:

• lenA = 5, lastNodeofA = node 5
• lenB = 5, lastNodeofB = node 5
• Same last node, so intersection exists

Align Starting Points:

• diff = |5 – 5| = 0
• Both lists have same length, no alignment needed

Walk Together:

• Compare node 1 and node 3: different, continue
• Compare node 2 and node 6: different, continue
• Compare node 8 and node 8: same! Return node 8

Result: Intersection at node 8

Time and Space Complexity

• Time Complexity: O(m + n) – We traverse each list a few times but still linear
• Space Complexity: O(1) – We only use a few variables

Simplifying It

This approach is like two runners on a track where one starts ahead. We calculate how far ahead one is, then give the other runner a head start so they both have the same distance remaining. When they start running together, they’ll meet at the finish line (intersection point).

Solution 3: Optimal Approach (Two Pointers with List Switching)

Intuition

Here’s a brilliant trick! Imagine two friends trying to meet, but they’re on different paths of different lengths. Instead of calculating distances, they agree on this rule: “When I reach the end of my path, I’ll start walking on your path from the beginning.” If their paths intersect, they’ll definitely meet at the intersection point because they’ll both have walked the same total distance!

Detailed Approach

1. Set Up Two Pointers: Start both pointers at the heads of their respective lists
2. Walk and Switch: When a pointer reaches the end of its list, redirect it to the head of the other list
3. Keep Moving: Both pointers will eventually walk the same total distance
4. Meet at Intersection: If the lists intersect, the pointers will meet at the intersection node
5. No Intersection: If lists don’t intersect, both pointers will become null at the same time

Code

class Solution:
    def getIntersectionNode(
        self, headA: ListNode, headB: ListNode
    ) -> Optional[ListNode]:
        if not headA or not headB:
            return None  # If either list is empty, no intersection possible

        temp1, temp2 = headA, headB  # Two pointers starting at respective heads

        # Keep moving until both pointers meet
        while temp1 != temp2:
            if temp1 is not None:
                temp1 = temp1.next      # Move to next node in current list
            else:
                temp1 = headB           # Switch to other list when current ends
            
            if temp2 is not None:
                temp2 = temp2.next      # Move to next node in current list
            else:
                temp2 = headA           # Switch to other list when current ends

        return temp1  # Return intersection node (or None if no intersection)

Code Explanation

This elegant solution uses two pointers that traverse both lists in a special way. Each pointer walks through its own list first, and when it reaches the end, it switches to the other list. This ensures both pointers walk the same total distance: length of list A + length of list B. If the lists intersect, the pointers will meet at the intersection point. If they don’t intersect, both pointers will become null simultaneously, and the loop will end.

Dry Run

Let’s trace through:

• List A: 1 -> 2 -> 8 -> 4 -> 5 (length = 5)
• List B: 3 -> 6 -> 8 -> 4 -> 5 (length = 5)

Step-by-step traversal:

• temp1=1, temp2=3: different, continue
• temp1=2, temp2=6: different, continue
• temp1=8, temp2=8: same! Return node 8

Actually, let me trace a more interesting example:

• List A: 4 -> 1 -> 8 -> 4 -> 5 (length = 5)
• List B: 5 -> 6 -> 1 -> 8 -> 4 -> 5 (length = 6, intersects at node with value 8)

Traversal:

• Initially: temp1 at 4 (A), temp2 at 5 (B)
• After a few steps: temp1 finishes A, switches to B; temp2 continues in B
• Later: temp2 finishes B, switches to A; temp1 continues in B
• Eventually: Both pointers meet at the intersection node

Key insight: temp1 travels A_length + B_length, temp2 travels B_length + A_length. Same total distance!

Result: Intersection found at the common node

Time and Space Complexity

• Time Complexity: O(m + n) – Each pointer traverses at most both lists once
• Space Complexity: O(1) – We only use two pointer variables

Simplifying It

This approach is like two people agreeing to walk each other’s routes. Person A walks route A then route B, while Person B walks route B then route A. Since they walk the same total distance, if their routes intersect, they’ll meet at the intersection point. It’s a beautiful mathematical solution that requires no extra calculations!

Summary

The optimal approach is generally preferred because it’s the most elegant and uses constant space while maintaining the same time efficiency. However, the brute force approach is more intuitive and easier to understand when you’re first learning about intersection problems.

All three solutions effectively solve the problem with the same time complexity, but the optimal solution is the most beautiful because it leverages a mathematical insight: if two people walk the same total distance on intersecting paths, they’ll meet at the intersection. This technique is widely applicable and demonstrates the power of clever pointer manipulation in linked list problems!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.