To find the Nth node from last when visited nodes are getting deleted

So the question is : find kth node frm last in a linked list if nodes a disappearing once read.Thi开发者_Go百科s should be done in one pass only.

Try avoiding extra memory .

I am aware of the trivial solution to this problem where two pointers(P and Q lets say) to the header node are taken and P of them is incremented N times and after that both pointers are incremented.The pointer Q points to the Nth last element.

But the question is somewhat different here .here the nodes are disappearing once they are read so there is no way the two pointer way could be used .

And kindly don't close the question before reading it. because this question is different .

Thanks

---

Keep on storing K elements somewhere, for example if K is 6, then store 6 latest read nodes somewhere as you traverse the linked list, and on reading next node, store that and remove the oldest read node from those you have stored. Once the linked list ends, you will have the last K elements stored (use a linked list or an array etc for this), and the Kth element from the last will be the oldest stored element.

this may not be the most efficient solution as i was typing while i was thinking, but it should work.

---

1. Create a queue of size K
2. Sequentially read each element of the list.
3. As each node is read, make a copy of node and enqueue onto the queue. If queue is full, dequeue the queue as well.
4. After reading the last node in the list, dequeue the queue. This is the K-to-last element.