GATE CS Mock 2018

Question

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

Comments

http://coderevisited.com/finding-the-intersection-point-of-two-linked-lists/

https://www.geeksforgeeks.org/write-a-function-to-get-the-intersection-point-of-two-linked-lists/

---

Method 6 (Traverse both lists and compare addresses of last nodes)

Traverse the list 1, store the last node address
2) Traverse the list 2, store the last node address.
3) If nodes stored in 1 and 2 are same then they are intersecting

Still i'm not getting this solution ):

sir can you explain this ?

---

@Nikhil
Suppose there are two linked lists L1 and L2. If both linked lists intersect somewhere then will meet at the end. It means the last node address will be same in both the linked list. This problem is same as there are two ways to reach a common destination.

But if two linked lists don't meet anywhere then their last node address will not be same.

T.C is O(m+n).

---

Correct Solution: https://www.geeksforgeeks.org/gate-gate-cs-mock-2018-question-30/

Answer 1

• 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.

Comments

But this approach needs extra space of O(m+n). What will be time complexity of no extra storage is provided, O(m*n)?

---

 Great solution @abhishekmehta4u

But 1 silly Doubt : Compare both array in O(m+n) is it similar to merge procedure ?

finding common element two array i thought it will be O( n² )

please correct me :D

---

Yes you are right .

For comparing we can apply similar for merge procedure.

Answer 2

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).

Comments

what do you mean by traversing in lock mode??

---

Lock mode traversal means traverse both linked lists together as long as you get the same element.

Answer 3

• 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)$