I want to know what's the meaning of intersection


  • 0

    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..


  • 0
    A

    "intersection" means the same address, not value


  • 3
    S

    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).


  • 0
    Z

    Ok, I got it. Thank you for your nice explanation. I just put myself in a corner. :)


  • 0
    D

    "after two lists merge, they can never branch out again" - this definitely helps me understand the question. Thanks.


  • 0
    I

    The problem doesnt say "if two node of the list", so they must be part of the same list linked. For example if I have {2, 3, 4, 5, 6, 7 } {9, 3, 7 ,11 ,4, 5, 6 ,7 }


  • 1
    S

    @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.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.