Question
//leetcode.com/problems/intersection-of-two-linked-lists/description/
Write a program to find the node at which the intersection of two singly linked lists begins.
Example:
A: a1 a2 c1 c2 c3 B: b1 b2 b3begin to intersect at node c1.
Notes:
- If the two linked lists have no intersection at all, return null.
- The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O[n] time and use only O[1] memory.
Thought Process
- Set
- Add all the node to hashset from list A
- checking the node exist in the hashset or not
- Time complexity O[m]
- Space complexity O[m + n]
- Two Pointers
- Each pointer points to the start of the list, pA and pB
- When pA reach the end, we reinitialize to head of B, opposite thing happens for pB
- If the end of list for A and B is not the same, we have no intersection
- Otherwise, they will eventually meet