Reverse a singly-linked list with and without using recursion

Question

I am new to data structures, and I know this is a very common question to ask. But I know LinkedList in .NET is doubly-linked, so how I will write code for a singly-linked list in C#.

Could someone please write sample code?

Answer 1

You need to define a node data structure which contains some data and a reference to the next node in the linked list. Something like:

class Node {
  private Node _next;
  private string _data;

  public Node(string data) {
    _next = null;
    _data = data;
  }

  // TODO: Property accessors and functions to link up the list
}

Then you can write an algorithm to loop over the list in reverse order, constructing a new reversed list.

Answer 2

reversed_list = new
for all node in the original list
   insert the node to the head of reversed_list

Answer 3

Use loop (current element: currentNode, variables initialzied outside loop: previousNode, nextNode)

Set nextNode = currentNode.NextNode
Set currentNode.NextNode = previousNode
Set previousNode = currentNode
Set currentNode = nextNode
continue with loop

Answer 4

Since this is likely homework, I'm going to state this in a way that might be pretty confusing so as not to do all the work. Hopefully my attempt doesn't just make things more confusing (which is highly possible).

When you have a reference to a node in the list (say the first node), you also have a reference to the node that follows it. You just need to make the following node refer to your current node while keeping enough information around about the following node (and its previous state) to perform similar work for it. Now the only tricky parts are dealing with the boundary conditions (the start and the end of the list).