160. Intersection of Two Linked Lists - cocoder39/coco39_LC GitHub Wiki

160. Intersection of Two Linked Lists

(a + c) + b = (b + c) + a

what if there is no intersection? Imaging the case below where d3 is None

headA--d1---
            |-d3--nullptr
headB--d2---

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB # a will go through every none-None node and one None node
            b = b.next if b else headA
        return a

below solutions works if there is guaranteed an intersection. otherwise it will falls into endless loop because the intersection is None but neither a nor b can reach it

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        a, b = headA, headB
        while a != b:
            a = a.next if a.next else headB # a will go through every non-None node
            b = b.next if b.next else headA # b will go through every non-None node
        return a

=================================================================

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { 
        ListNode *p1 = headA;
        ListNode *p2 = headB;
        while (p1 != p2) {
            p1 = p1 ? p1->next : headB;
            p2 = p2 ? p2->next : headA;
        }
        return p1;
    }