Looking at the discussion post, the most upvoted comment clearly hinted at the solution, but what did it mean?
"If I wander to the end of the world and still cannot find you, I will
take another path and search anew."
"And I shall do the same, my love." – dinguming102
"And I shall do the same, my love." – dinguming102
My Thoughts
- What if they missed each other?
- What if they only meet at the next node after the intersection?
I will explain why they eventually meet, using two pointers.
Understanding the Concept
Imagine two linked lists of different lengths having an intersection, e.g.:
A: [3, 6, 3, 7, 1, 4, 2, 5, 10]
B: [2, 5, 10]If we concatenate A + B and B + A, their lengths become the same:
A + B: [3, 6, 3, 7, 1, 4, 2, 5, 10, 2, 5, 10]
B + A: [2, 5, 10, 3, 6, 3, 7, 1, 4, 2, 5, 10]Since we move both pointers one step at a time from position 0, 1, 2, etc., no node is skipped. Thus, the pointer starting from A and the pointer starting from B will eventually intersect.
Smart move! Learning all these helps me get more creative. Until next time!