Linked lists - Common element

Question : Find if two linked lists contain a common suffix given their start pointers and lengths, identify the first common element.

Answer :

1. Traverse through the first linkedlist ( LL 1 ) to find it's length. Let's say it is m. Keep track of it's last pointer. (the one before null).

2. Traverse through the second linkedlist ( LL 2 ) to find it's length. Let's say it is n. If the last pointer here is same as the one in step 1, then both linkedlists are intersecting. And go to step 3

3. Now compare m and n. Let's say m > n. Then the first point where the intersection "is possible" is at position m-n. Simply traverse through the first linkedlist till m-n positions. As you continue to traverse LL1 from this position, start traversal of LL2 and compare the pointers @ each position. Wherever the pointers equate that is where the two lists intersect.

Complexity : In the worst case it requires traversing through the two linkedlists twice. O(4n) ~ O(n). So it is O(n) algorithm.