Hiii ...
If we are given two linked lists (may be of different length) such that a few nodes from the end are common ... How do we find the first common node in least time as possible ... ?
The lists are singly linked . Some nodes are common from the end and we need to find the first common one for both among them FROM THE END.
Assuming each linked list has a completely unique set, the only method I see is to use a nested for loop which would be terribly inefficient. If the data sets are not unique you could use a third (linked) list as a cache of only unique nodes but your still looking at a worst case of O(n²)
Total complexity: O(n)
For example:
1->2->3->4->7->8
---------5->6->7->8
We expect to get 7 since it's the first common node.
An O(n) solution to find the first node in one of the lists with the same value. You can then extract the value from that node.
All code sections (comments) are O(1) unless otherwise specified and there are no nested O(n) operations. Hence the entire solution is O(n).
It works by counting the elements in each list then advancing the pointer for the longest list so that the ends are aligned.
Then it steps through both lists in a synchronised fashion. If the nodes match and haven't previously matched, it saves that node (not just if they match since you want the earliest match in a sequence).
If they don't match, you save that fact so that a subsequent match will be considered the earliest in the sequence.
By the time you get to the end of both lists, you either have an indication that there was no match (if the final node of both lists are different) or the earliest match in the sequence.
Pseudo-code only of course, since it's homework:
def findCommonNode (head1, head2):
# Work out sizes O(n)
set count1 and count2 to 0
set ptr1 to head1
while ptr1 is not equal to NULL:
increment count1
set ptr1 to ptr1->next
set ptr2 to head2
while ptr2 is not equal to NULL:
increment count2
set ptr2 to ptr2->next
# If either size is 0, no match possible.
if count1 == 0 or count2 = 0:
return NULL
# Make the first list longer (or same size).
if count1 < count2:
swap count1 and count2
swap head1 and head2 (local copies only)
# Move through longest list until they're aligned O(n).
set ptr1 to head1
set ptr2 to head2
while count1 is greater than count2:
decrement count1
set ptr1 to ptr1->next
# Initially mark as non-match.
set retptr to NULL
# Process both (aligned) lists O(n).
while ptr1 is not equal to NULL:
# If equal and if first match after non-match, save position.
if ptr1->data is equal to ptr2.data:
if retptr is equal to NULL:
set retptr to ptr1
else:
# If not equal, mark as non-match.
set retptr to NULL
# Advance to next element in both lists.
set ptr1 to ptr1->next
set ptr2 to ptr2->next
# Return the earliest match.
return retptr
Let's say you have the two lists 1,2,3,4,5,5,6,7,8,9 and 0,6,9,8,9. Aligning these and advancing the list 1 pointer based on the size difference, you'll get:
v
1 2 3 4 5 5 6 7 8 9
0 6 9 8 9
^
Then you set match to NULL and start processing. They don't match (5/0) so you set the first matching node to NULL (even though it's already NULL) and advance to 6/6.
These (6/6) do match (and the current match is NULL) so you save the address of one of them as the match, and advance.
7/9 does not match so you once again set the match to NULL, then advance.
8/8 matches and the match is NULL so you once again set the match to one of them, then advance.
9/9 also matches but match is already set so you don't change it. Advance then and your out of elements in both lists.
You then return the match with is one of the 8 nodes. And that's your earliest match for a common trailing section.