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 take another look. I removed the reversing one, and replaced it with one that destroys the next pointers, and and another that modifies the vals. Along with the 2 pointer one, these should all work. I think it needs some cleanup though. Let me know what you see.
The 2-pointer solution is mostly good. Three things I see:
1. There's a typo ("heead") on line 76 which causes errors on lists of unequal length.
2. It enters an infinite loop when the intersection is None, i.e. the lists don't actually intersect. This is okay going by the problem statement, but in an interview I'd follow up the question by asking you to extend it to handle this case.
3. You probably want to compare the nodes directly on line 70 rather than their vals - you are only guaranteed that the example is free of nodes with duplicate vals, not that all possible inputs are.
As you note, the other two solutions are destructive, so they can't be implemented where the inputs are const.
The tilde solution has additional problems:
1. You store an extra char per node, so it fails the requirement of constant space.
2. It doesn't generalise well: you can't implement this for val types that don't have a string representation, or for string vals where the input might begin with a literal tilde (Unix filepaths, for instance).
Apart from trashing the input data, the last algorithm can't safely be implemented in a non-garbage-collected language. You can't free each node while traversing the m-list because the intersection node still has to be there when you traverse the n-list, but you leak any nodes you don't free.
I spoke with a colleague over lunch today and we got into solutions for finding cyclical linked lists. So taking from the discussion we had, I wanted to see if I could implement it. Unfortunately, none of these except the bad list reversal one are my own design. The two pointer solution was suggested in a similar problem on LeetCode. So basically, I wanted to implement it and see it work. I just had a few minutes between work and the gym, so I wanted to get something up. Definitely not grade A code.
Ultimately the two pointer solution is likely what they were looking for. Certainly can use some code cleanup. At least some error checking. :)
The code isn't that bad, you just have to be careful you don't go down a dead end with your algorithm. It's much easier to add error checking etc. at the end if you designed a versatile solution than it is to try and generalise one of the more brittle ones.
Would you mind if I suggested a challenge? I have one involving graph manipulation, which is kind of up @freemo's alley.
Interesting, that interleaving of the if/else and the while loop is very strange to my eye but it's cool that Python allows it.
The nondestructive one looks solid now; the destructive one still claims to find an intersection in disjoint lists though.
🇳🇱
@khird @freemo It is pretty well cleaned up now. and I fleshed out the list a little to make it iterable and printable and stuff. Take a peek!
Please suggest one, just remember to include the hash tag
#toyprogrammingchallenge