Question:
Hello.
Quite often, at interviews or in test tasks (for an internship, for example), a question is asked about singly linked lists .
For example, they give a problem in which it is necessary to expand a singly linked list in O(n) time. So here's how to do it? Is it possible to just redefine links? Those. to do in 1 iteration so that not A->B , but A<-B ?
Can you please give an example? Thank you in advance
Answer:
Well, stand on the first element, and going through the list, each unfold the pointer to the previous node from which you just came. It is clear that the very first pointer is reset to zero, and the head of the list now points to the node that was last. That's O(n) .