Logo
    Logo

    ©️ 2020-2026, Akhil Abraham.

    LinkedInGitHubMediumX
    Akhil Abraham
    Akhil Abraham
    /Posts
    Posts
    /LeetCode
    LeetCode
    /
    LeetCode
    /0160 - Intersection of Two Linked Lists
    0160 - Intersection of Two Linked Lists
    0160 - Intersection of Two Linked Lists
    0160 - Intersection of Two Linked Lists

    0160 - Intersection of Two Linked Lists

    Difficulty
    Easy
    Language
    Python
    URL
    https://leetcode.com/problems/intersection-of-two-linked-lists/

    Solution 1 - Hash Set

    Traverse the first linked list and store each node reference in a hash set. Then traverse the second linked list and check if any node already exists in the set. The first match is the intersection point.

    TimeComplexity:O(m+n)TimeComplexity: O(m + n)TimeComplexity:O(m+n)
    SpaceComplexity:O(m)SpaceComplexity: O(m)SpaceComplexity:O(m)

    Solution 2 - Two Pointer Technique

    Use two pointers starting at the heads of each list. When a pointer reaches the end of its list, redirect it to the head of the other list. Both pointers will traverse the same total distance (m + n), so they will meet at the intersection node or both reach None if there is no intersection.

    TimeComplexity:O(m+n)TimeComplexity: O(m + n)TimeComplexity:O(m+n)
    SpaceComplexity:O(1)SpaceComplexity: O(1)SpaceComplexity:O(1)
    """ 0160.1 - Intersection of Two Linked Lists - Solution 1 - Hash Set """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class ListNode:
    """ListNode Class"""

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


class Solution:
    """Solution Class"""

    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        """Intersection of Two Linked Lists Function"""
        seen = set()

        current = headA
        while current:
            seen.add(current)
            current = current.next

        current = headB
        while current:
            if current in seen:
                return current
            current = current.next

        return None


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Build intersection: 8 -> 4 -> 5
    common = ListNode(8)
    common.next = ListNode(4)
    common.next.next = ListNode(5)

    # List A: 4 -> 1 -> 8 -> 4 -> 5
    headA = ListNode(4)
    headA.next = ListNode(1)
    headA.next.next = common

    # List B: 5 -> 6 -> 1 -> 8 -> 4 -> 5
    headB = ListNode(5)
    headB.next = ListNode(6)
    headB.next.next = ListNode(1)
    headB.next.next.next = common

    result = Solution().getIntersectionNode(headA, headB)
    print(result.val if result else None)  # 8


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

    """ 0160.2 - Intersection of Two Linked Lists - Solution 2 - Two Pointer Technique """

#####################################################################################
# Imports
#####################################################################################
from typing import Optional

#####################################################################################
# Classes
#####################################################################################
class ListNode:
    """ListNode Class"""

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


class Solution:
    """Solution Class"""

    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        """Intersection of Two Linked Lists Function"""
        a, b = headA, headB

        while a is not b:
            a = a.next if a else headB
            b = b.next if b else headA

        return a


#####################################################################################
# Functions
#####################################################################################
def testcase():
    """Test Function"""
    # Build intersection: 8 -> 4 -> 5
    common = ListNode(8)
    common.next = ListNode(4)
    common.next.next = ListNode(5)

    # List A: 4 -> 1 -> 8 -> 4 -> 5
    headA = ListNode(4)
    headA.next = ListNode(1)
    headA.next.next = common

    # List B: 5 -> 6 -> 1 -> 8 -> 4 -> 5
    headB = ListNode(5)
    headB.next = ListNode(6)
    headB.next.next = ListNode(1)
    headB.next.next.next = common

    result = Solution().getIntersectionNode(headA, headB)
    print(result.val if result else None)  # 8

    # No intersection
    headC = ListNode(1)
    headD = ListNode(2)
    result2 = Solution().getIntersectionNode(headC, headD)
    print(result2)  # None


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()