Intersection of Two Linked Lists

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given two linked list, find the first link at which the two lists intersect

Why This Works

(Explain the core reason the solution is correct.)

• Sets has $O(1)$ lookup of existing item

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Linked List

Time & Space Complexity

• Time: $O(n+m)$ → Reason: Looping through each item in both lists once
• Space: $O(n)$ → Reason: Storing a full copy of one of the lists

Code

class Solution:
    def getIntersectionNode(
        self, headA: ListNode, headB: ListNode
    ) -> Optional[ListNode]:
        nodesOfA = set()

        cur = headA
        while cur:
            nodesOfA.add(cur)
            cur = cur.next

        cur = headB
        while cur:
            if cur in nodesOfA:
                return cur
            cur = cur.next

        return None

Optimized Time & Space Complexity

• Time: $O(n+m)$ → Reason: Looping through each list once
• Space: $O(1)$ → Reason: Not storing another copy of the list

Why This Works

(Explain the core reason the solution is correct.)

• First we figure out the length of each list
• Once we know the length, we basically know the difference between the two lists
• If we iterate the longer list by the difference then we will get at the spot thats the same length on both
• Now, from this point iterating both lists together we can find the first element that is equal to each other and that's our answer.

Optimized Code

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
        lenghtA = 0 # 5
        cur = headA
        while cur:
            lenghtA += 1
            cur = cur.next

        lenghtB = 0 # 6 
        cur = headB
        while cur:
            lenghtB += 1
            cur = cur.next

        newHead = None
        diff = abs(lenghtA - lenghtB) # 1
        newHead = headA if lenghtA > lenghtB else headB
        for _ in range(diff):
            newHead = newHead.next
        headA = newHead if lenghtA > lenghtB else headA
        headB = newHead if lenghtB > lenghtA else headB
        
        while headA and headB:
            if headA == headB:
                return headA
            headA = headA.next 
            headB = headB.next 
        return None