Reversing single linked list in C#
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.
Node p = root, n = null;
while (p != null) {
Node tmp = p.next;
p.next = n;
n = p;
p = tmp;
}
root = n;
Years ago I missed out on a hipster-L.A.-entertainment-company ASP.NET MVC developer position because I could not answer this question :( (It's a way to weed out non-computer-science majors.) So I am embarrassed to admit that it took me way too long to figure this out in LINQpad using the actual LinkedList<T>
:
var linkedList = new LinkedList<int>(new[]{1,2,3,4,5,6,7,8,9,10});
linkedList.Dump("initial state");
var head = linkedList.First;
while (head.Next != null)
{
var next = head.Next;
linkedList.Remove(next);
linkedList.AddFirst(next.Value);
}
linkedList.Dump("final state");
The read-only LinkedListNode<T>.Next
property is what makes LinkedList<T>
so important here. (Non-comp-sci people are encouraged to study the history of Data Structures---we are supposed to ask the question, Where does the linked list come from---why does it exist?)