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]`↵
2. add 8 at 1st index in list => `list = [5, 8, 6, 7]`↵
2. 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))↵
In the original problem the elements to be inserted are between 0 to n-1
↵
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]`↵
2. add 8 at 1st index in list => `list = [5, 8, 6, 7]`↵
2. 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))↵
In the original problem the elements to be inserted are between 0 to n-1
