We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Intersection of Two Linked Lists

Number: 160

Difficulty: Easy

Paid? No

Companies: Microsoft, Amazon, Google, LinkedIn, Meta, Apple, TikTok, Accenture, Nvidia, Uber, Bloomberg, Airbnb

Problem Description

Given the heads of two singly linked lists headA and headB, return the node at which the two lists intersect. If the linked lists have no intersection, return null. Note that the intersection is defined by reference, not by value.

Key Insights

  • The intersection point is defined by reference (i.e., the same memory location), not by the node value.
  • Using two pointers that traverse both lists can help align the pointers so they traverse an equal number of nodes.
  • When one pointer reaches the end of its list, it switches to the head of the other list.
  • If the linked lists intersect, the pointers will eventually meet at the intersection node; if not, both will become null.

Space and Time Complexity

Time Complexity: O(m + n)
Space Complexity: O(1)

Solution

We use a two-pointer approach. Initialize two pointers, one at headA and one at headB. Traverse the lists by moving each pointer one step at a time. When a pointer reaches the end of its list, reset it to the head of the other list. This aligns the pointers so that if there is an intersection, they will meet at the intersecting node. If not, both pointers will eventually become null, indicating no intersection. This approach runs in O(m + n) time and uses constant extra space.

Code Solutions

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        # If either list is empty, there is no intersection.
        if not headA or not headB:
            return None
        
        ptrA = headA  # Pointer for list A
        ptrB = headB  # Pointer for list B
        
        # Loop until the two pointers are the same.
        while ptrA != ptrB:
            # If pointer A reaches the end, switch to headB; otherwise move to the next node.
            ptrA = headB if ptrA is None else ptrA.next
            # If pointer B reaches the end, switch to headA; otherwise move to the next node.
            ptrB = headA if ptrB is None else ptrB.next
        
        # Either both pointers point to the intersection node or are both None.
        return ptrA
← Back to All Questions