Member Avatar for vskumar19

Consider a single linked list with 'n' nodes and other single linked list with 'm' nodes
At the 'k'th node in 'n' ,the second linked list merges at some part of it .. jst like the shape Y

Now i was asked to find out the address of Kth node

I did it by taking the address of the each node in an array and compared with the address of the 2nd linked list with a time complexity of O(n*m)

But i was asked to reduce the time complexity .. even assuming that 'n' and 'm' are equal

Is there any possible method to reduce the time complexity other than O(n*n) ??

  • 2 Contributors
  • 2 Replies
  • 108 Views
  • 7 Hours Discussion Span
  • Latest Post Latest Post by vskumar19
Member Avatar for Adak

What about using a binary search pattern on the addresses of the shorter link? (same size links, then choose either one). If at a given node the addresses are == then lo moves up to current position + 1. Next comparison would be 1/2 that far up the link. If not equal addresses are found, then move the hi marker, down, etc.

And instead of putting all the node addresses into an array, leaving them alone, and working with the sizeof(node) as the smallest increment/decrement size for the search?

Should bring it down to O(log N) on average. Maybe.

Member Avatar for vskumar19

you cant say that the addresses are in sorted order !!!
so i guess u cant use a binary search for that..

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.