160. Intersection of Two Linked Lists

Solution 1: Brute-Force

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        while headA:
            ptrB = headB
            while ptrB:
                if headA == ptrB:
                    return headA
                ptrB = ptrB.next
            headA = headA.next
        return None

Time Complexity: O(M*N)
Space Complexity: O(1)

Solution 2: Hash + Bitmap

# 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) -> Optional[ListNode]:
        nodeAddr = {} # {Node: Cnt}
        while headA:
            nodeAddr[headA] = True
            headA = headA.next
        while headB:
            if headB in nodeAddr:
                return headB
            nodeAddr[headB] = True
            headB = headB.next
        return None

Time Complexity: O(M + N)
Space Complexity: O(M + N)

Solution 3: Difference

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        ptrA, lenA = headA, 0
        ptrB, lenB = headB, 0
        # Count LenA, LenB
        while ptrA:
            ptrA = ptrA.next
            lenA += 1
        while ptrB:
            ptrB = ptrB.next
            lenB += 1
        
        # Remove additional node before intersect
        lenDiff = abs(lenA - lenB)
        if lenA > lenB:
            while lenDiff:
                headA = headA.next
                lenDiff -= 1
        else:
            while lenDiff:
                headB = headB.next
                lenDiff -= 1
        
        # Scan & Compare ListNode
        ans = None
        while headA and headB:
            if headA == headB:
                ans = headA
                break
            headA = headA.next
            headB = headB.next
        return ans

Time Complexity: O(M + N)
Space Complexity: O(1)

Solution 4: Two Pointer

# 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) -> Optional[ListNode]:
        ptrA = headA
        ptrB = headB
        
        # We want to repeatedly scan until
        # 1. ptrA == ptrB == None, or
        # 2. ptrA == ptrB    
        while ptrA != ptrB:
            # Scan ListA
            if ptrA == None:
                ptrA = headB 
            else:
                ptrA = ptrA.next
            
            # Scan ListB
            if ptrB == None:
                ptrB = headA
            else:
                ptrB = ptrB.next
        return ptrA # or ptrB

Time Complexity: O(M + N)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/1093014/C%2B%2B-Four-different-solutions