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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Intersection of Two Linked Lists

Difficulty: Easy

Problem Description

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.

Key Insights

  • The two linked lists may intersect at a node, meaning they share the same reference in memory.
  • We need to identify the first node where the two lists overlap.
  • A straightforward approach involves using a hash table to track visited nodes, but we can solve this more efficiently with two pointers.
  • The two-pointer technique allows us to traverse both lists in O(m + n) time with O(1) space.

Space and Time Complexity

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

Solution

To solve this problem, we can use the two-pointer technique. We initialize two pointers, one for each linked list. We will traverse both lists until they meet. If one pointer reaches the end of its list, we redirect it to the head of the other list. This way, both pointers will traverse the same total length when they intersect. If they reach the end without meeting, it means there is no intersection.

Code Solutions

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

def getIntersectionNode(headA, headB):
    if not headA or not headB:
        return None

    pointerA, pointerB = headA, headB

    while pointerA != pointerB:
        pointerA = pointerA.next if pointerA else headB
        pointerB = pointerB.next if pointerB else headA

    return pointerA
← Back to All Questions