Reverse a singly-linked list with and without using recursion

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

Could someone please write sample code?

---

Here it is using recursion.

private void Reverse(Item item)
    {
        if (item == null || item.Next == null) //if head is null or we are at the tail
        {
            this.Head = item; //we are at the tail or empty list, set the new head to the tail
            return;
        }

        Reverse(item.Next);

        var nextItem = item.Next; //get the next item out, dealing with references don't want to override it
        item.Next = null;         //once you get the next item out, you can delete the *reference* i.e. link to it
        nextItem.Next = item;     //set the item you got out link to next item to the current item i.e. reverse it
    }

---

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

---

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.

---

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

---

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

---

//Have tried the Iterative approach as below, feel free to comment / optimize 

package com.test;


public class ReverseSinglyLinkedList {


public ReverseSinglyLinkedList() {
    // TODO Auto-generated constructor stub
}
public Node ReverseList(Node n)
{

    Node head =  n; 
    Node current = n; 
    Node firstNodeBeforeReverse = n;  // keep track of origional FirstNode

    while(true) 
    {

        Node temp = current; 
         // keep track of currentHead in LinkedList "n", for continued access to unprocessed List
        current = current.next; 
        temp.next = head;
          // keep track of head of Reversed List that we will return post the processing is over 
        head = temp;   

        if(current.next == null)
        {

            temp = current;
            current.next = head;
            head = temp;        
                            // Set the original FirstNode to NULL
            firstNodeBeforeReverse.next = null; 

            break;
        }
    } 

    return head;

}

public void printLinkList(Node n)
{

    while(true)
    {
        System.out.print(n.data + " ");
        n = n.next;
        if(n.next ==null)
        {
            System.out.print(n.data + " ");
            break;
        }

    }
}

public static void main(String[] args) {
    // TODO Auto-generated method stub

    // TEST THE PROGRAM: crate a node List first to reverse it
    Node n = new Node(1);
    n.next = new Node(2);
    n.next.next = new Node(3);
    n.next.next.next = new Node(4);
    n.next.next.next.next = new Node(5);
    n.next.next.next.next.next = new Node(6);

    ReverseSinglyLinkedList r = new ReverseSinglyLinkedList();
    System.out.println("Input Linked List : ");  
    r.printLinkList(n);

    Node rsList = r.ReverseList(n);

    System.out.println("\n Reversed Linked List : ");
    r.printLinkList(rsList);



}

}

---

Here is linked reversal iterative and recursive in .net (C#) (note the linked list is maintaining both first and last pointers so that i can append at the end or insert at head in O(1) - one doesn't have to do this. I just defined my linked list behavior as above)

public void ReverseIterative()
        {
            if(null == first)
            {
                return;
            }
            if(null == first.Next)
            {
                return;
            }
            LinkedListNode<T> p = null, f = first, n = null;
            while(f != null)
            {
                n = f.Next;
                f.Next = p;
                p = f;
                f = n;
            }
            last = first;
            first = p;
        }

Recursive:

        public void ReverseRecursive()
        {
            if (null == first)
            {
                return;
            }
            if (null == first.Next)
            {
                return;
            }
            last = first;
            first = this.ReverseRecursive(first);
        }
        private LinkedListNode<T> ReverseRecursive(LinkedListNode<T> node)
        {
            Debug.Assert(node != null);
            var adjNode = node.Next;
            if (adjNode == null)
            {
                return node;
            }
            var rf = this.ReverseRecursive(adjNode);
            adjNode.Next = node;
            node.Next = null;
            return rf;
        }