Algorithm Question.. Linked List

Question

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.

is http://stackoverflow.com/questions/1801549/reverse-a-singly-linked-list what you want? — Aif, May 22 '10 at 17:23
Are There any other efficient solution available apart from using stack implementation,, Also How can we implement the same using recursion.. — AGeek, May 22 '10 at 17:28
Do you think recursion suits any problem very well? I can't think of a convincing reason why *not* to use recursion here. — Daniel Harms, May 22 '10 at 18:24
@Precision: Imagine a huge list. You could overflow the stack if you used recursion. — , May 22 '10 at 19:00
Fair enough. Then a single pass in place algorithm would be the best fit. — Daniel Harms, May 22 '10 at 19:03
A singly-linked list _is_ a stack when you only hold on to the head of the list! Use it as one, and you're practically done. (If you don't understand how a singly linked list is a stack, think about the two fundamental operations you can use in a stack, and the equivalent operations in a singly linked list.) — Rex Kerr, May 22 '10 at 19:59

score 4 · Answer 1 · answered May 22 '10 at 17:27

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;
}

answered May 22 '10 at 17:27

sth

222,467
53
283
367

This. The stack solution is still O(n), but it is definitely less efficient than single traversal with pointer twiddling. – Amadan May 22 '10 at 17:28
3

This is homework. Do you really want to provide a complete solution? – Robert Harvey May 22 '10 at 17:30

Robert Harvey · Answer 2 · 2010-05-22T17:29:25.433

2

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.

edited May 22 '10 at 17:29

answered May 22 '10 at 17:22

Robert Harvey

178,213
47
333
501

score 2 · Answer 3 · answered May 22 '10 at 17:26

2

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.

answered May 22 '10 at 17:26

catchmeifyoutry

7,179
1
29
26

score 1 · Accepted Answer · answered May 22 '10 at 21:05

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:

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

score 0 · Answer 5 · answered May 22 '10 at 17:23

0

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

answered May 22 '10 at 17:23

Dimitris Andreou

8,806
2
33
36

score 0 · Answer 6 · answered May 22 '10 at 18:35

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.

Algorithm Question.. Linked List

6 Answers6