Intersection of Linked List

2 min read
LC-Easy
Linked List

Oct 21, 2022

3 years ago

LeetCode

Solution

Brute force solution is iterate through both lists, add nodes to hash set. Whenever a node that was already added is seen, return that node. But this uses extra memory.
Iterate through both lists until one reaches null, when it does, set it to the head of the other linked list
- If we were given the lengths of both the lists, we can traverse the longer list until the number of nodes remaining in both is the same-- then we can just traverse both lists at the same pace until they meet at the intersection point
  - I.e. traverse the longer list by the difference in lengths, then do a normal traversal of both linked lists
- We are not given the lengths, however it is easy to find them. But then our solution would be O(2n), which is good, but we can do better
- The idea is that both lists have the same end node, when one list reaches the end, it is set to the head of the other node
  - It is basically doing the same thing as traversing the longer node with the difference in lengths
  - If we do one list at a time, A would traverse 5 times, then it would be set to B, then it would traverse 6 times until it reaches null
    - B would traverse 6 times, then it would be set to A, and it would traverse 5 times until it reaches null.
      - Here they're intersecting at the end. We just do both of these steps together so that they intersect at the first actual intersection point

Time	Space	Explanation
`O(n)`	`O(1)`

def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]: l1, l2 = headA, headB while l1 != l2: l1 = l1.next if l1 else headB l2 = l2.next if l2 else headA return l1