Algorithm Question.. Linked List..

Question

Hi,

Scenario is as follows:-

I want to reverse the direction of the singly linked list, In other words, after the reversal all pointers should now point backwards..

Well the algorithm should take linear time.

The solution that i have thought of using another datastructure A Stack.. With the help of which the singly linked list would be easily reversed, with all pointers pointing backwards.. But i am in doubt, that whether the following implementation yeild linear time complexity.. Please comment on this.. And if any other efficient algorithm is in place, then please discuss..

Thanks.

Answer 1

If you put all of the nodes of your linked list in a stack, it will run in linear time, as you simply traverse the nodes on the stack backwards.

However, I don't think you need a stack. All you need to remember is the node you were just at, to reverse the pointer of the current node. Make note of the next node before you reverse the pointer at this node.

Answer 2

For a list of size n, you call n times push and n times pop, both of which are O(1) operations, so the whole operation is O(n).

Answer 3

2 times O(N) = O(2*n) is still O(N). So first push N elements and then popping N elements from a stack is indeed linear in time, as you expected.

See also the section Multiplication by a Constant on the "Big O Notation" wikipedia entry.

Answer 4

You could do it like this: As long as there are nodes in the input list, remove its first node and insert it at the beginning of the output list:

node* reverse(node *in) {
   out = NULL;
   while (in) {
      node = in;
      in = in->next;
      node->next = out;
      out = node;
   }
   return out;
}

Answer 5

You can use a stack to achieve a O(n) implementation. But the recursive solution IS using a stack (THE stack)! And, like all recursive algorithms, it is equivalent to looping. However, in this case, using recursion or an explicit stack would create a space complexity of O(n) which is completely unnecessary.

Answer 6

The previous answers have and already (and rightly) mentioned that the solution using pointer manipulation and the solution using stack are both O(n).

The remaining question is to compare the real run time (machine cycle complexity) performance of the two different implementations of the reverse() function.

I expect that the following two aspects might be relevant:

1. The stack implementation. Does it require the maximum stack depth to be explicitly specified? If so, how is that specified? If not, how the stack does memory management as the size grows arbitrarily large?

2. I guess that nodes have to be copied from list to stack. [Is there a way without copying?] In that case, the copy complexity of the node needs to be accounted for. Thats because the size of the node can be (arbitrarily) large.

Given these, in place reversal by manipulating pointers seems more attractive to me.