How do you solve Intersection of Two Linked Lists on LeetCode?

Intersection of Two Linked Lists (LeetCode #160) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Both lists must be traversed fully to ensure all nodes are checked for intersection.

What is the time complexity of Intersection of Two Linked Lists?

The optimal solution for Intersection of Two Linked Lists runs in O(n) time and uses O(1) space. This complexity is linear because each pointer traverses at most two lists, leading to a total of n steps in the worst case.

What is the brute force solution for Intersection of Two Linked Lists?

The brute force approach for Intersection of Two Linked Lists is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every node in one list against every node in the other list to find the intersection. This is simple but inefficient, especially for long lists. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Intersection of Two Linked Lists?

Intersection of Two Linked Lists uses the following concepts: Hash Table, Linked List, Two Pointers. The recommended patterns to study are: Two Pointers, Linked List.

What are the interview tips for Intersection of Two Linked Lists?

Clearly explain your thought process before coding. Consider edge cases and mention them during the interview. Test your solution with different scenarios, including no intersection.

What are common mistakes when solving Intersection of Two Linked Lists?

Not considering edge cases where one or both lists are empty. Assuming that the values of nodes are unique when checking for intersection.

#160

Intersection of Two Linked Lists

Easy

Hash TableLinked ListTwo PointersTwo PointersLinked List

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

The optimal solution uses two pointers to traverse both lists. By switching the pointers to the head of the other list after reaching the end, we ensure both pointers traverse the same distance when they meet, thus finding the intersection efficiently.

⚙️

Algorithm

3 steps

1Step 1: Initialize two pointers, pointerA at headA and pointerB at headB.
2Step 2: Traverse both lists; if pointerA reaches the end, redirect it to headB, and similarly for pointerB.
3Step 3: If the pointers meet, return the intersection node; if they both reach the end (null), return null.

solution.py13 lines

1class ListNode:
2    def __init__(self, val=0, next=None):
3        self.val = val
4        self.next = next
5
6def getIntersectionNode(headA, headB):
7    if not headA or not headB:
8        return None
9    pointerA, pointerB = headA, headB
10    while pointerA != pointerB:
11        pointerA = pointerA.next if pointerA else headB
12        pointerB = pointerB.next if pointerB else headA
13    return pointerA

ℹ

Complexity note: This complexity is linear because each pointer traverses at most two lists, leading to a total of n steps in the worst case.

1Both lists must be traversed fully to ensure all nodes are checked for intersection.
2Using two pointers allows us to avoid extra space and achieve linear time complexity.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.