Geek Answers Handbook

To find the Nth node from the last when visiting nodes, delete

So the question is: find kth node frm last in the linked list if nodes a disappearing once read . This should be done in one go.

Try to avoid extra memory.

I am aware of a trivial solution to this problem, where two pointers (P and Q) are taken into the node header, and P increases them N times, and after that both pointers increase. Pointer Q points to the last element of N.

But the question here is somewhat different: where the nodes disappear after reading them, so you cannot use two pointer methods.

And do not kindly close the question before reading it. because this question is different.

thanks

+4
source share
2 answers

Continue to store the elements of K somewhere, for example, if K is 6, then store the last 6 read nodes somewhere when you cross the linked list, and when reading the next node, store this and delete the oldest read node from the ones you saved. As soon as the linked list is over, you will save the last K-elements (use a linked list or array, etc.), and the Kth element from the last will be the oldest saved element.

this may not be the most effective solution, as I typed when I thought, but it should work.

+6
source
  • Create K Queue
  • Read each item in the list sequentially.
  • As you read each node, make a copy of the node and put it in the queue. If the queue is full, delete the queue in the queue.
  • After reading the last node in the list, delete the queue. This is a K-to-last element.
+1
source

More articles:


All Articles