This question has already been answered:
- Theory on a single-linked list 2 answers
How can I deploy it using O (n) time and O (1) memory?
strunct Node { int payload; Node *next; }; Node* head; 
Denis
8,358 6 nineteen 49
mr.robot mr.robot
sixteen five
Reported as a duplicate by participants Harry , aleksandr barakin , D-side , Grundy , Athari 19 Apr '16 at 21:12 .
A similar question was asked earlier and an answer has already been received. If the answers provided are not exhaustive, please ask a new question .
- Instead of screenshots, please post the code. (And then there is a chance to get a photo of the monitor / paper with the solution) - Nick Volynkin ♦
- oneI have already seen this question 2 times here) - pavel
- I don’t see through the search - mr.robot
- 7ru.stackoverflow.com/questions/272/… ru.stackoverflow.com/questions/509477/… - pavel
|
2 answers
Insert at the beginning of the list O (1) in time and memory. Therefore, you can do this: get a new empty list, bypass the old one by inserting each element at the beginning of a new one. Total it will turn out just O (1) on memory and O (n) on time.
VladD VladD
183k sixteen 223 433
|
Without inserting into a new one, just go through the list, expanding the field next each element, to the previous one. For the former first one, the next field is reset, head set to the former last element.
In fact, in general, the same thing as inserting into a new one ..
Harry Harry
106k 9 54 132
|