Linked list algorithm

If it's mutable, just step through and reverse the direction of the rest reference; if it's not, do the same building a new list.

Eg:class Cons {

Object first;

Cons rest;

Cons (Object first, Cons rest) {

this.first = first;

this.rest = rest;

}

public String toString () {

final StringBuffer buffer = new StringBuffer();

buffer.append('[');

buffer.append(first);

for (Cons list = rest; list != null; list = list.rest) {

buffer.append(", ");

buffer.append(list.first);

}

buffer.append(']');

return buffer.toString();

}

}

public class ReverseList {

static Cons cons (Object first, Cons rest) {

return new Cons(first, rest);

}

public static void main (String[] args) {

Cons list = cons("A", cons("B", cons("C", cons("D", null))));

echo(list);

echo(reverse(list));

echo(list);

echo(nreverse(list));

echo(list);

echo();

list = null;

echo(list);

echo(reverse(list));

echo(list);

echo(nreverse(list));

echo(list);

}

static Cons reverse (Cons list) {

Cons tail = null;

for (; list != null; list = list.rest) {

tail = cons(list.first, tail);

}

return tail;

}

static Cons nreverse (Cons list) {

Cons prev = null;

for (Cons rest; list != null; list = rest){

rest = list.rest;

list.rest = prev;

prev = list;

}

return prev;

}

static void echo () {

System.out.println("");

}

static void echo (Cons list) {

if (list == null) {

System.out.println("[]");

} else {

System.out.println(list);

}

}

}

Pete

pm_kirkhama at 2007-7-10 2:52:50 >