Domain 1EasyCORE

Intersection of Two Linked Lists

The problem requires finding the intersection node of two singly linked lists, `headA` and `headB`. If there is no intersection, the function should return `null`. The constraints guarantee that there are no cycles in the linked lists. The goal is to solve this problem with an `O(n)` time complexity and `O(1)` space complexity.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Linked List

160. Intersection of Two Linked Lists

Model: qwen2.5-coder:14b
Topics: Linked List
FAANG asked: 1
Acceptance rate: 44.5%


Problem Breakdown

The problem requires finding the intersection node of two singly linked lists, headA and headB. If there is no intersection, the function should return null. The constraints guarantee that there are no cycles in the linked lists. The goal is to solve this problem with an O(n) time complexity and O(1) space complexity.

Inputs:

  • Two singly linked lists, headA and headB.

Outputs:

  • The node at which the two lists intersect, or null if they do not intersect.

Implicit Constraints/Edge Cases:

  • The linked lists may have different lengths.
  • If there is no intersection, return null.
  • The solution should be efficient in terms of both time and space.

Intuition

A brute-force approach would involve checking each node in headA against every node in headB, resulting in a time complexity of O(m * n). This is inefficient for large lists. A better approach involves leveraging the fact that if we traverse both lists, they will eventually meet at the intersection point if one exists. By aligning the lengths of the two lists, we can ensure that when we traverse them simultaneously, we will either find the intersection or reach the end of both lists.

Approach

  1. Calculate Lengths: Traverse each list to determine its length.
  2. Align Lengths: Move the pointer of the longer list forward by the difference in lengths so that both pointers are at the same distance from the potential intersection point.
  3. Traverse Simultaneously: Move both pointers one step at a time until they either meet (at the intersection node) or reach the end of their respective lists.

This approach ensures that we traverse each list at most twice, resulting in an O(n) time complexity and O(1) space complexity.

Complexity Analysis

  • Time Complexity: O(m + n), where m is the length of headA and n is the length of headB. We traverse each list once to calculate its length and then traverse them again to find the intersection.
  • Space Complexity: O(1), as we only use a constant amount of extra space for pointers.

Solution

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

def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode:
    # Helper function to calculate the length of a linked list
    def get_length(node):
        length = 0
        while node:
            length += 1
            node = node.next
        return length
    
    # Calculate lengths of both lists
    lenA, lenB = get_length(headA), get_length(headB)
    
    # Align the pointers by moving the longer list's pointer forward
    if lenA > lenB:
        for _ in range(lenA - lenB):
            headA = headA.next
    else:
        for _ in range(lenB - lenA):
            headB = headB.next
    
    # Traverse both lists simultaneously to find the intersection
    while headA and headB:
        if headA == headB:
            return headA
        headA, headB = headA.next, headB.next
    
    # If no intersection is found, return null
    return None

Edge Cases Handled

  • No Intersection: The function returns null if the lists do not intersect.
  • Different Lengths: The approach handles lists of different lengths by aligning them before traversal.
  • Single Node Lists: The solution works correctly even if one or both lists contain only a single node.