CODEWITHSUNDEEP
cdata-structureslinked-list
mohan.t
mohan.t

Reputation: 277

Find the common nodes of two intersecting linked lists

I was asked in the interview that if we have two linked list which intersect in more that one node then how can we find the common nodes in which the linked list meet. Also find the solution with minimum complexity.

e.g. 

      ![Linked List example][1]

Linked List 1 = 11->12->13->14->15->16->17->54

Linked List 2 = 23->24->13->26->14->15->35->16->45

I answered him that we can store addresses of one linked list in hashmap and compare every node's address in second list with the hashmap. This way we can achieve O(n) complexity. But the interviewer was not satisfied.

Please suggest any better solution. Thanks in advance.

Upvotes: 0

Views: 3836

Answers (3)

Ofir Dror
Ofir Dror

Reputation: 1

my suggested solution:

you create a hashmap, iterate the first list, and for each element you do: hashMap.put({value}, "firstList");

on O(n) you get a map of elements.

iterate the second list, for each element ask: hash_map.containsKey({number}) ?

if so, intersectionCounter ++;

the best is O(N) i think.

this is what i would do.

Upvotes: 0

Sunny Aggarwal
Sunny Aggarwal

Reputation: 53

it can be achieved in a better way listen if two linked list are intersecting at some node so we can traverse ones both the list find the length of each list then move the pointer of one list upto the distance between the two &then move both the pointer simultaneouly int his way whenever u get the that node both the pointers are equal..

  1. Given two singly linked list, find if they are intersecting. Do this in single iteration.

    a. traverse list1 and find the last element

    b. traverse list2 and find the last element

    c. check if last element of list1 == last element of list2 , if equal intersecting else not

here we have parsed the list only once :-)

  1. Also find the intersecting node in O(n) time and O(1) space here they have asked to do it in O(1) space so we need to use only one variable :-)

    a. create a variable(int) diff=0

    b. parse list1 and increment diff for each node

    c. parse list2 and decrement diff for each node

    d. if diff is > 0 list1 is bigger so push the pointer of list1 by diff times else list2 is bigger so push the pointer of list2 by mod(diff) times

    e. Now check if both the pointers are equal till we reach end

Upvotes: 1

Ron Teller
Ron Teller

Reputation: 1890

If the values are integers and you have unlimited memory, you can perform the following:

  1. Traverse each list once and find the global maximal value MAX
  2. Allocate a boolean array A with the size of MAX
  3. Traverse one list, for each value X in the list set A[X] = true
  4. Traverse the second list, for each value Y in the list if A[Y] = true then Y is a list intersection

This runs with O(N) time (which I believe you can't do better as the lists are not sorted)

Upvotes: 0

Related Questions