Most of the solutions presented by above fellows missed a curical point in the initial statement. i am repeating.
"nth element from end"
now if you look the solutions , most people prefered to traverse from head of the link list to nth element but how do you know the size of link list and how can you be sure that it is nth element which is to be deleted unless you travel from end. So therefore, these above solutions will generate a bug in the solutions.
Similarly the answer to this problem can be tricky depending upon the way link list been implemented. But if we consider the implementation standards by Java or STL then it can be implemented by O(1). Here is how
1.Make a member of Class which keep track the no of nodes .
2. Calculate the Target node by
Target Node = Size - N
3. Remove the Node N (Order of O(1) )
For reference please have a look at Introduction to Algorithms (Corman,MIT Press).
|