Hacker News Reader

Comment by coffeemug | Hacker News Reader

When you ask someone to reverse a linked list, do you mean 'in place'?

I 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.

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.

Just 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.

They'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.

One 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.

Unless 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

Reply on news.ycombinator.com