Today I will describe about easy but with interesting solution problem – Intersection of Two Linked Lists. OK, let’s read problem description:
Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists:
[crayon-5bf05b464e030473961029/] begin to intersect at node c1. Notes:
If the two linked lists have no intersection at all, return
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.
So, what can we see? We have two linked lists where last part can be the same, like in the pic above. OK, try to think how to find first element of the common part.
First solution can be based on two loops. Run two loops for each element of list1 check all elements of list2, yes, complexity will be bad and equals to O(nm) if n ==m , O(n^2), but we do not use additional memory.
Second one can be based on recursion. Main idea run through 2 lists to the end and in back way compare each element. If elements are not equal return next one. Complexity will be O(n+m) ~ O(n), but memory usage will be O(n+m) which is not good. Code example:
Third one solution can be based on the set. Run through list1, store all elements in set and after that run through list2 check if element is present it’s intersection return it if no, return null. Complexity will be O(n+m) ~ O(n), but memory usage will be O(n+m) which is not good (can be O(n) or O(m)). Code example:
OK, all solutions are not good, so, we can use a trick:
- Counts lengths of both lists.
- Counts difference between them.
- Run through bigger list to different length, for align both lists
- Run through both lists and compare elements.
Hmm, perfect lest implement it:
[crayon-5bf05b464e044003529517/] So, leetcode accepted that solution, that is good, complexity as written in task description O(n) and memory O(1). Perfect! Thanks.