4,007 views
1 votes
1 votes

Suppose there are two singly linked lists both of which intersect at some point and become a single linked list. The head or start pointers of both the lists are known, but the intersecting node and lengths of lists are not known. What is worst case time complexity of optimal algorithm to find intersecting node from two intersecting linked lists?

A)Θ(n*m), where m, n are lengths of given

B) listsΘ(n^2), where m>n and m, n are lengths of given lists
 
C) Θ(m+n), where m, n are lengths of given lists
 
D) Θ(min(n, m)), where m, n are lengths of given lists

3 Answers

1 votes
1 votes
  • Traverse the first list and store the address an array
  • Traverse the second list and store the address an another array .
  • Compare both array if array if address is same then link list is intersecting.
  • Traversing both array so time complexity become O(m+n)
  • In this example if we store in the array then both array contain address 30 . So there is a intetsecting point.

1 votes
1 votes

Answer is : - C

Algorithm goes like this :--

Step 1 - Find out length of both linked lists , which takes :- Q(m+n).

Step 2 - Reverse both linked lists which again takes :- Q(m+n).

Step 3 - Traverse in lock mode as long as you get same items  which O(min(m,n)).

Step 4 - At the end of step 3 you get the intersecting node.

 Step 5 - Reverse linked lists back , which takes Q(m+n).

Hence time complexity comes out to be Q(m+n).

0 votes
0 votes
  • Traverse First lists and Find M and N

                                                       time complexity =$ O(n)$

  • Traverse larger list till |M-N| elements 

                                                       time complexity =$ O(1)$

  • Traverse both linked inside a single loop and find the same element by comparing elelments after each iteration

                                                    time complexity =$ O min(m,n)$

  • total time complexity =$ O(m+n+min(m,n))=O(m+n)$
  • Space complexity = $O(1)$

Related questions

0 votes
0 votes
0 answers
4
Ram Swaroop asked Jan 3, 2019
638 views
Which of the following functions describe the graph shown in the below figure? (A) y=||x|+1|−2(B) y=||x|−1|−1(C) y=||x|+1|−1(D) y=||x|−1|−1|