4 ms·
Making the candidates reverse a linked list over the phone? Either the job market is worse than I thought or somebody is power-tripping something awful.
by hernan7 16y ago
Making the candidates reverse a linked list over the phone? Either the job market is worse than I thought or somebody is power-tripping something awful.
- coffeemug 16y agohttp://typewith.me/ http://typewith.me/
- tkahn6 16y agoWhen you ask someone to reverse a linked list, do you mean 'in place'?
- mjw 16y agoI wondered that too. My first thought was to build it up again from new conses, as you would in lisp. But then spotted a neat in-place way to do it too. Found I absolutely had to draw a few scribbly diagrams first though.
- weaksauce 16y agoThe 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.
- sfk 16y agoOne of the main points of linked lists is that you can manipulate the structure (sort, reverse, etc.) without copying the payloads. So in C, always in place unless explicitly specified otherwise.
- tkahn6 16y agoUnless you're dealing with primitive data types, aren't your payloads just pointers (to structs or null-terminated strings)? Or is it more usual to allocate space within the node and memcpy the bits in? I've always wondered that. Thanks