N insertion in a list

Revision en1, by SevenDeadlySins, 2019-11-12 23:43:23

I recently had to solve this problem for a test, but was not able to find an efficient solution for the same.

Is it possible to make 'n' insertions to a linked list efficiently when we are given the positions of all insertion, and the element which has to be inserted.

Eg: position = [0,1,2,1,2] , elements = [5,6,7,8,9], list = []

So basically the operations we would be doing are

  1. add 5 at 0th index in list => list = [5]
  2. add 6 at 1st index in list => list = [5, 6]
  3. add 7 at 2nd index in list => list = [5, 6, 7]
  4. add 8 at 1st index in list => list = [5, 8, 6, 7]
  5. add 9 at 2nd index in list => list = [5, 8, 9, 6, 7]

So the final list would be [5, 8, 9, 6, 7]

Does anyone know an efficient solution for the same? (better than O(n^2))

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English SevenDeadlySins 2019-11-12 23:45:02 74
en1 English SevenDeadlySins 2019-11-12 23:43:23 805 Initial revision (published)