Second Freebie!!! This one is marked as "easy"
This problem was asked by Google.
Given two singly linked lists that intersect at some point, find the intersecting node. The lists are non-cyclical.
For example, given A = 3 -> 7 -> 8 -> 10 and B = 99 -> 1 -> 8 -> 10, return the node with value 8.
In this example, assume nodes with the same value are the exact same node objects.
Do this in O(M + N) time (where M and N are the lengths of the lists) and constant space.
Okay, so my solution didn't meet the O(n+m) complexity. But Iound the correct algorithm, and both are in place and the code is updated. @freemo this was kind of interesting, reminds me of an old card trick I used to do.
@Absinthe Are you sure you interpreted the problem correctly? It seems your solution only works with non-intersecting lists that just happen to have the same numbers at the end.
For instance your solution breaks if I change the beginning of main() to the following:
common = Node(8,Node(10));
mlist = LList(Node(3,Node(7,common)))
nlist = LList(Node(99,Node(1,common)))
@khird yes, you are absolutely right. I heard another solution today that may also work that I want to try. And it will require that the nodes are more correct like you are doing them. As I have it with your changes the second reverse should scramble it. But if you only reverse one of them you could go through a while until the n.next.next == n. I may get away with a destructive version as well. Check later.
