[Coderust] Intersection of Two Linked Lists

 

 

Problem

 

 

 

 

---

 

Solution

 

If one list is longer than the other, ignore the leading part and start at the point where the total number of nodes will be the same.

Compare one by one, and if none of the nodes are equivalent, return null.

 

 

# 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]:
        if not headA or not headB:
            return None
        
        lengthA = -1
        lengthB = -1
        pA = headA
        pB = headB
        
        while pA:
            lengthA += 1
            pA = pA.next
            
        while pB:
            lengthB += 1
            pB = pB.next
            
        pB = headB
        pA = headA
        if lengthA > lengthB:
            for _ in range(lengthA-lengthB):
                pA = pA.next
        else:
            for _ in range(lengthB-lengthA):
                pB = pB.next
        
        while pA:
            if pA == pB:
                return pA
            pA = pA.next
            pB = pB.next
        
        return None

 

Time Complexity

O(N)

 

Space Complexity

O(1)