the two linked lists, ln1={2,3,4,5}, ln2={9,3,7,5}. Do they have the intersection or not?
the intersection is 3 or 5?
Anyone can give some explanations? so confused..
In general, you cannot tell whether two linked lists are intersected solely based on the values of the nodes. For the purpose of online judging, however, we deliberately assign a unique value for each node. So in our test cases, the value can be regard as sort of a unique id for the node; if both linked lists have a node with the same value, then this node must be part of their intersection.
In your example, it seems that the lists merge first at 3, then detach from each other, then merge again at 5. This is not possible because after two lists merge, they can never branch out again. They can be: {2, 3, 4, 5} / {9, 3, 4, 5} (intersect at 3) or {2, 3, 7, 5} / {9, 1, 4, 5} (intersect at 5).
@ignacio2 yes i didnt say that in the prob description, because it is not something a user needs to know, and you shouldn't rely on this property to solve this prob. It is designed that way so the users would have an easier time spotting their mistakes. Alternatively, if I show the address instead of the value, you will have a hard time visualizing the linked structure. If you find my answer above hard to understand, think of it this way: the node 3 doesn't mean ANY node whose val is 3, but rather it is the 3rd node. Therefore node 3 cannot be the precursor of both 4 and 7, so your case is impossible.