160. Intersection of Two Linked Lists - python3

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

begin to intersect at node c1.

Other Answer 1:

# 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:
        
        hA = headA
        hB = headB
        
        while hA!=hB:
            hA = headB if not hA else hA.next
            hB = headA if not hB else hB.next
        
        return hA

뒷목잡고 쓰러질뻔한 초간단 코드

Other Answer 2: hashset, two-pointer, and concise two-pointer

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:  # hashset
        seen = set()
        for head in (headA, headB):
            while head:
                if head in seen:
                    return head
                seen.add(head)
                head = head.next

1) hashset

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:  # two-pointer, O(1) space
        if headA is None or headB is None:
            return
        node_a, node_b = headA, headB
        while True:
            if node_a == node_b:
                return node_a
            if node_a.next == node_b.next:
                return node_a.next
            node_a = node_a.next if node_a.next else headB
            node_b = node_b.next if node_b.next else headA

2) two-pointer

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:  # more concise
        if headA and headB:
            node_a, node_b = headA, headB
            while node_a is not node_b:
                node_a = headB if node_a is None else node_a.next
                node_b = headA if node_b is None else node_b.next
            return node_a

3) concise two-pointer