Bueno, de nuevo otra pregunta, la cual busca ver si usted puede manejar algoritmos complejos:

¿Como se puede ordenar de atrás para adelante una lista simplemente enlazada, sin crear estructuras de datos adicionales?

Muchas compañias preguntan acerca de listas simplemente enlazadas ya que su implementación es sencilla y se puede realizar en el tiempo programado para una entrevista; Este problema tiene muchas soluciones, una que me gustó bastante (y de la cual no me atribuyo la solución) la encontré en un enlace en la Universidad de Stamford, toda ella llena de problemas interesantes de listas, es la de los 3 apuntadores.

Primero, una implementación básica de un nodo de la lista:

   1:/**
   2: * This class models a 'String' node on a list.
   3: * @author Jose V Nunez Zuleta
   4: * @version 0.1 - 03/07/2005
   5: * Blog: El Angel Negro - http://elangelnegro.blogspot.com
   6: * License: GPL
   7: */
   8:public class Node {
   9:
  10:        protected String value;
  11:        protected Node next;
  12:    
  13:        /**
  14:         * Parametric constructor
  15:         * @param value
  16:         * @since 0.1
  17:         */
  18:        public Node(String value) {
  19:                this.value = value;
  20:        }
  21:    
  22:        /**
  23:         * Show the internal state of the object
  24:         * @return String
  25:         */
  26:        public String toString() {
  27:                if (next != null) {
  28:                        return "{" + value + "," + next.value + "}";
  29:                } else {
  30:                        return "{" + value + ", null}";
  31:                }
  32:        }
  33:}

Y luego el código que hace la ordenación de atrás para delante:

   1:/**
   2: * Common <a href="http://cslibrary.stanford.edu/105/LinkedListProblems.pdf">algorithms</a> 
   3: * for single linked lists
   4: * @author Jose V Nunez Zuleta
   5: * @version 0.1 - 03/07/2005
   6: * Blog: El Angel Negro - http://elangelnegro.blogspot.com
   7: * License: GPL
   8: *
   9: */
  10:public class Lists {
  11:    
  12:        /**
  13:         * Stores the arguments in a list and performs list manipulations
  14:         * @param args - List of arguments to convert
  15:         * @throws Exception If list is empty
  16:         */
  17:        public static void main(String [] args) {
  18:            
  19:                if (args == null) {
  20:                        throw new
  21:                                IllegalArgumentException("Provide some nodes");
  22:                }
  23:            
  24:                if (args.length == 0) {
  25:                        throw new
  26:                                IllegalArgumentException("Provide some nodes");
  27:                }
  28:                int len = args.length;
  29:                Node head = new Node(args[0]);
  30:                for (int i = 1; i < len; i++) {
  31:                        append(head, new Node(args[i]));
  32:                }
  33:                iterate(head);
  34:                head = reverse(head);
  35:                iterate(head);
  36:        }
  37:
  38:        /**
  39:         * Show the contents of the single linked list.
  40:         * @param head
  41:         */
  42:        public static void iterate(Node head) {
  43:                Node current = head;
  44:                while (current != null) {
  45:                        System.out.print(current);
  46:                        if (current.next != null) {
  47:                                System.out.print(" ");
  48:                        }
  49:                        current = current.next;
  50:                }
  51:                System.out.println();
  52:        }
  53:    
  54:        /**
  55:         * Add elements at the end of the list
  56:         * @param head List head
  57:         * @param node Node to add at the end.
  58:         */
  59:        public static void append(Node head, Node node) {
  60:                Node current = head;
  61:                while (current.next != null) {
  62:                        current = current.next;
  63:                }
  64:                current.next = node;
  65:                node.next = null;
  66:        }
  67:    
  68:        /**
  69:         * Reverse a single linked list without using an additional structure.
  70:         * This algorithm uses three pointers (bac, middle and front) to keep
  71:         * track of the changes.
  72:         * This method is not recursive.
  73:         * @param head Head of the list
  74:         * @return The new head of the list.
  75:         */
  76:        public static Node reverse(Node head) {
  77:                if (head == null) {
  78:                        return head;
  79:                }
  80:                Node middle = head;
  81:                Node front = middle.next;
  82:                Node back = null;
  83:                while(true) {
  84:                        middle.next = back;
  85:                        if (front == null) {
  86:                                break;
  87:                        }
  88:                        back = middle;
  89:                        middle = front;
  90:                        front = front.next;
  91:                }
  92:                return middle;
  93:        }
  94:}

Ojo, antes que salga un purista con que mi implementación de una lista es muy tosca, si eso ya lo sé. De hecho no está bien ‘orientada a objeto’ y modela muy cerca lo que usted haría en un lenguaje como C.

¿Como la mejoraría?

Aqui tiene el código como de costumbre.