""" 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()
