Not bad, but anything beyond the original solution...

2010-10-26T23:02:31.724+02:00

Not bad, but anything beyond the original solution introduces extra constant time slowdown. Now if the interview candidate could sufficiently argue why that is irrelevant (compiler optimizations, or optimize 80-20 rule, etc) then that would be pretty impressive.

Alexandru, using the "compiler's internal stack" is equivalent to O(n) memory usage where n is the # of nodes in the linked list, so it fails to satisfy the problem constraint of O(1) memory usage.

What about recursion? Isn't that easier to imp...

2009-10-14T13:04:19.559+02:00

What about recursion? Isn't that easier to implement and more elegant?

Here's a suggestion:

ListNode invertList(ListNode currN, ListNode succN) {
ListNode startN = null;

if( succN.next != null ) startN = invertList(succN, succN.next);
else startN = succN;
succN.next = currN;

return startN;
}

It should be called as
newFirstNode = invertList( null, firstNode );

It's basically the same principle that you described but it's using the compiler's internal stack. Therefore we work on the initial list (and there's no need to create a new list/stack). This means less memory to use.

What do you think?

Comments on Codility: The Power of Good Design

Not bad, but anything beyond the original solution...

What about recursion? Isn't that easier to imp...