I have a linked list of n nodes , i want to delete a kth node and display the element in it. This is easy if the value of n is relatively small and complexity of the problem is not a issue.
The problem is when i have n nodes in the linked list where n >=200000 and i want to delete a node which is also a relatively great value (say k=150000).
The normal solution to this problem is traverse the whole linked list and delete a node (where the complexity of the solution is O(n) ), though it is straight forward and easy solution it takes more time. Other solution to this problem can be having 2 pointers but still that is not optimal solution.
I am looking for a solution which is optimal and provides result in minimal amount of time.
Hope my question is clear. Need some help..
Use SkipList concept.
It is like using Express Lanes or Highway Roads, to reach to the desired node at the fastest possible speed (by choosing minimal traversal length).
You need to create multiple layers so that you can skip some nodes without any hesitation.
TC: Same average running time as Binary Search Tree O(log n).
Doesn't requires complex reorganisation of the given linked list.