reverse list without deleting the initial list

Question

I'm trying to reverse a list, but l want to keep my initial list. My function reverse doesn't keep the initial list

For example I want to reverse this:

Node n = new Node(1,new Node(12, new Node(34, new Node(3, Node.NIL))));

and my function is:

public Node reverse(){

  Node p= this;
  if(p == NIL)
      return Node.NIL;


  if(p.n == Node.NIL)
      return p;

  Node rest = p.getNext();
  p.setNext(Node.NIL);
  Node reverseRest = rest.reverse();

  rest.setNext(p);
  return reverseRest;
}

The length of my old list after the reverse is 1, and I want it to be 4 for this example. My old and my new list have to have the same length after the reverse.

Answer 1

In order to preserve the original list your reverse method must create new Nodes objects, rather than making modifications to existing ones.

If you would like to write a recursive reverse() that takes no parameters, you can do it as follows:

• Make a new Node, and copy this node's content into it; set next to NIL
• If the next of this node is NIL, return the result of previous step
• Otherwise, call reverse() on the next
• Take the return value from the previous call, and navigate to its end
• Add the new node from step one to the end, and return the result.

A better approach is to change the signature of reverse to take the nodes created so far, in reverse order. This would produce an O(n) algorithm, while the unmodified algorithm above is O(n²).