3 ms·
The in place way is O(N) whereas I cannot think of a way to do it for less than O(N^2) building up the list the other way.
by weaksauce 16y ago
The in place way is O(N) whereas I cannot think of a way to do it for less than O(N^2) building up the list the other way.
- kenjackson 16y agoJust copy the addresses of each node in the list to an array. Then you can make copies of each node and reverse the copy in O(n) -- if you want to do it in O(n) out-of-place.
- chc 16y agoThey're both O(N). Pseudocode for the other way: 1. copy head of list consed with nil 2. copy next item consed with previous 3. goto 2 while next item is not nil That's N*(cost of a copy and a cons). Granted, it's not as fast in absolute terms, but the slowdown is a constant factor. You're certainly not doing N operations on each item.