IntersectionOfTwoLinkedLists

Problem

https://leetcode.com/problems/intersection-of-two-linked-lists/

Solution

Use a set to store the nodes in the first linked list with headA. Then, check if any node in the second linked list with headB is in the set.

Code

from typing import List


class ListNode:
    """Node in a linked list.
    """

    def __init__(self, val: int, next: ListNode | None = None) -> None:
        self.val = val
        self.next = next

    @classmethod
    def from_list(cls, list: List[int]) -> ListNode | None:
        head: ListNode | None = None
        for el in list:
            if head is None:
                head = ListNode(el)
                node = head
            else:
                node.next = ListNode(el)
                node = node.next
        return head


def getIntersectionNode(headA: ListNode, headB: ListNode) -> ListNode | None:
    """Gets the first node where two linked lists intersect. Returns ``None``
    if there is no intersection.
    """
    setA = set()
    while headA is not None:
        setA.add(headA)
        headA = headA.next

    while headB is not None:
        if headB in setA:
            return headB
        headB = headB.next
    return None

Test

>>> from IntersectionOfTwoLinkedLists import ListNode, getIntersectionNode
>>> a = ListNode.from_list([4, 1, 8, 4, 5])
>>> b = ListNode(5, ListNode(0, ListNode(1, a.next.next)))
>>> getIntersectionNode(a, b).val
8
>>> a = ListNode.from_list([0, 9, 1, 2, 4])
>>> b = ListNode(3, a.next.next.next)
>>> getIntersectionNode(a, b).val
2
>>> a = ListNode.from_list([2, 6, 4])
>>> b = ListNode.from_list([1, 5])
>>> getIntersectionNode(a, b) is None
True
class IntersectionOfTwoLinkedLists.ListNode(val: int, next: ListNode | None = None)

Bases: object

Node in a linked list.

classmethod from_list(list: List[int]) ListNode | None
IntersectionOfTwoLinkedLists.getIntersectionNode(headA: ListNode, headB: ListNode) ListNode | None

Gets the first node where two linked lists intersect. Returns None if there is no intersection.