The Gateway to Computer Science Excellence
0 votes
Given two unsorted singly-linked lists each with n distinct elements. There exists an efficient intersection algorithm, that computes and returns a new list with common elements between the input lists. How much time does the intersection algorithm requires in worst case, if it is allowed to use constant extra space only?
in DS by | 275 views
In my opinion optimal solution for is by HASHING

(i:e) ist unsorted  singly-linked list  = m size

       2nd unsorted singly linked list = n size

      and we also create an single linked list called "Intersection" where we store  our "result"

if m > n

we create a hash table of n size

1) one time traverse the whole linked list(2nd linked list) and insert it into the hash table

2)  linearly traverse the ist linked list and for each elements we check whether it's leads collision in the hash  table or not ?

whenever  there's a collision occurs we insert that element in out intersection linked list

2 times just linear traverse the linked list , therefore time complexity : O(m+n)
At max every elements in the list "m" is also present in the list "n"

So Worst case space complexity : O(m)

Soumya how?

Would it be feasible using hashing?

We traverse the first list and insert the elements in an empty hash table, which should take $O(n)$ time. Then, we traverse the second linked list and look it up in the table, which would take constant amount of time.  If it's present, we then append it to the Result list, which is where the results of the intersection are stored.
But question only permits constant space

it is allowed to use constant extra space only

Hashing is not feasible. 


I think efficient algorithm is 

  1. Using Merge sort for sorting both linked lists O(nlogn)
  2. Comparing  elements for both lists simultaneously O(n)

so O(nlogn) 

I missed only constant extra space is allowed so hashing cannot be performed.So we need to sort two linked list which will take O(nlogn) using merge sort and then traverse which will take O(2n) so overall in O(nlogn)
Merge sort is not inplace right ??

Read the merge sort blog shared by Utkarsh, it's inplace :)

Correct me if I'm wrong!

The question asked is to find intersection set of two linked list what you mentioned is to find the intersection point of two linked list forming Y shape.

Soumya both problems are somewhat linked to each other


@Soumya Tiwari the Time complexity is different


The one mentioned by Shaik is based on the structural alignment of the linked list.

And the question asked is to find intersection set based on the values in the linked list. I'm not able to identify the similarity between the two except brute force.

Correct me If I'm wrong!
Look for the merge sort of two unsorted linked list.

@Soumya Tiwari

without the values, how the structure is intersected ?

Why value is required here intersection point is the memory location common to both linked list....Isn't it?
Problem: Two linked lists list1 and list2 are joined a particular node, called the point of intersection of the linked lists. Find the point of intersection, i.e. the first node after which both lists have same nodes. Desired order is O(A + B) Time Complexity and O(1) Space Complexity Solution:

1: Find length of list1 – use a tmp1 node starting from head of list1 and move till last node.

2: Find length of list2 - use a tmp2 node starting from head of list2 and move till last node.

3: If tmp1 and tmp2 are different, it means that linked lists are non-intersecting. Return null.Example: list1: 1-2-3-4 , list2: 5-6-7-8, last nodes are separate.

4: Else set variables diff, tmp1 and tmp2 as: tmp1 (a list node) to head node of larger list. tmp2 (a list node) to head node of smaller list. diff (an integer) to difference of lengths of larger to smaller lists i.e. absolute difference of the lengths.

5: Move forward tmp1 by diff number of nodes.

6: Now lists starting from tmp1 and tmp2 have same number of nodes and intersect at a particular node. Therefore, both tmp1 and tmp2 are equidistant from the intersection node.

7: Starting from tmp1 and tmp2 simultaneously, move node by node till a common node is reached. This node is the intersection of the 2 lists.

I like ur procedure. Where is fault in it?

@Mk Utkarsh

I cannot understand how r u applying merge sort

Can u derive it more

And where is fault in @Magma's procedure?
For @magma it takes O(n) space


In java we have Hashmap which does similar function, but we need space to construct hashtable over there as well

@ kumar.dilip

Your algo finds the physical intersection of the two linked lists i.e. it finds whether two lists share some nodes with same address (and hence value).

Here we are asked to find the common values only and not the physical intersection.

Let LLs be represented like <value,address>. So if LL1 is <1,100>,<4,200> and LL2 is <4,300>, <3,400> then their intersection would be 4 even if there is no common node.

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
52,314 questions
60,435 answers
95,251 users