Single Chain Reverse List

Question

I hope I use the correct terminology. I made a list with one chain.

class MyStack { public Node Initial { get; set; } public MyStack() { Initial = null; } public void Push(int data) { var node = new Node { Data = data, Next = Initial }; Initial = node; } public int Pop() { int res = Initial.Data; Initial = Initial.Next; return res; } public int Sum() { int sum = 0; Node currentNode = Initial; while (currentNode != null) { sum += currentNode.Data; currentNode = currentNode.Next; } return sum; } public int Count() { int count = 0; Node currentNode = Initial; while (currentNode != null) { count++; currentNode = currentNode.Next; } return count; } public void PrintAll() { Node currentNode = Initial; while(currentNode != null) { Console.WriteLine("tmp.Data = " + currentNode.Data); currentNode = currentNode.Next; } } } public class Node { public int Data; public Node Next; } 

So you can do something like this:

  var s = new MyStack(); s.Push(5); s.Push(3); s.Push(7); s.PrintAll(); Console.WriteLine("Sum: " + s.Sum()); Console.WriteLine("Count: " + s.Count()); 

Now I want to try and do the opposite method. This seems to work:

 public void Reverse() { Node predesesor, location; location = Initial; predesesor = null; while(Initial != null) { Initial = Initial.Next; location.Next = predesesor; predesesor = location; location = Initial; } Initial = predesesor; } 

I can hardly see how this works, and it will be difficult to maintain. It seems like a hack than anything else.

Can you provide any help?

Answer 1

This doesn't seem like a hack to me, and I don’t see what needs to be supported there (is it either right or not, what else would you do with it?). If you want to figure out how this works, complete the “complete” step on paper. Draw a list (for example, 1 → 3 → 5 → 7 → 9 → NULL), mark where all the nodes indicate at any time and start the "one-step".

I could not think of a cleaner way to cancel a single list. You will need a link to the next node (Initial at the beginning of the loop) before you can reverse the relationship between the current node and the previous node. Otherwise, you simply cannot go to the original list.

What you can do is correct the spelling of the variables and possibly not use Initial in the loop itself (use the third variable, so the role of each variable is clearer) and set only Initial in the first node to the inverted list at the end.

So, all:

 public void Reverse() { Node current = Initial, previous = null; while (current) { Node next = current.Next; current.Next = previous; previous = current; current = next; } Initial = previous; } 

Answer 2

One solution would be to turn it into a doubly linked list, and then work backwards using the previous node property:

 public class Node { public int Data; public Node Next; public Node Previous; } 

There is already a doubly linked list in the framework if you want to save a little effort.

Answer 3

you can do it recursively:

 a->b->c->d a->null b->null c->null c<-d b<-c a<-b a<-b<-c<-d public void Reverse() { Reverse(Initial); } private void Reverse(Node node) { if(node != null && node.Next != null) { //go deeper Reverse(node.Next); //swap node.Next.Next = node node.Next = null; } } 

Answer 4

Instead of reinventing the wheel, you should check if there is something that you can use something from the .Net Framework .

For example, I would take a LinkedList here with a LinkedListNode . Other times, you could take Queue or Stack .

Answer 5

If you call it "nreverse" or "reverse in place", any appreciation from the developer can recognize it as a classic algorithm, not a hack.

It should not require significant maintenance, with the possible exception of renaming any incorrectly written variables.

Answer 6

The following code may be more intuitive:

 public void Reverse() { MyStack reverse = new MyStack(); while (Initial != null) { reverse.Push(this.Pop()); } Initial = reverse.Initial; } 

(The converse is a member method of the MyStack class).

Of course, this requires twice as much space as the source code.

Answer 7

 stack s1 s1.push_front(...) ... s1.push_front(...) 

//////////////////////////////////////////////////// //////

 void reverse(stack& to,stack_or_list& s ) while(!s.empty()){ to.push_front(s.pop_front()); } } 

now the to.pop_fronts series will deliver what you want

stack_or_list: pop_front empty to needs: push_front, pop_front