Reversing single linked list in C#

Question

I am trying to reverse a linked list. This is the code I have come up with:

 public static void Reverse(ref Node root)  {       Node tmp = root;       Node nroot = null;       Node prev = null;        while (tmp != null)       {           //Make a new node and copy tmp           nroot = new Node();               nroot.data = tmp.data;            nroot.next = prev;           prev = nroot;              tmp = tmp.next;        }        root = nroot;               } 

It is working well. Was wondering if it possible to avoid creating new node. Would like to have suggestions on this.

Answer 1

That question gets asked a lot. When I was asked it in my interviews many years ago, I reasoned as follows: a singly-linked list is essentially a stack. Reversing a linked list is therefore a trivial operation on stacks:

newList = emptyList; while(!oldList.IsEmpty())     newList.Push(oldList.Pop()); 

Now all you have to do is implement IsEmpty and Push and Pop, which are one or two lines tops.

I wrote that out in about twenty seconds and the interviewer seemed somewhat perplexed at that point. I think he was expecting me to take about twenty minutes to do about twenty seconds work, which has always seemed odd to me.

Answer 2

Node p = root, n = null; while (p != null) {     Node tmp = p.next;     p.next = n;     n = p;     p = tmp; } root = n;