itech9

From http://www.informatics.susx.ac.uk/courses/dats/notes/html/node46.html

public void reverse(ListNode head) {
    ListNode current = head;
    head = null;
    ListNode save = null;
    while (current != null) {
        save = current;
        current = current.next;
        save.next = head;
        head = save;
    }
}

http://en.allexperts.com/q/Computer-Science-3197/Bread-First-Search-Algorithm.htm

BFS(G, s)
 for each vertex u in V - { s } do
   u.color = white
   u.dist = infinity  // ''dist'' is distance from s
   u.pred = nil       // ''pred'' is predecessor
 s.color = gray
 s.dist = 0
 s.pred = nil
 Q = { s }            // ''Q'' is a FIFO queue
 while Q not empty do
   u = Q.head         // get element on top of queue
   for each v in neighbors(u) do  // visit every node u has an edge to
     if v.color == white then
       v.color = gray
       v.dist = u.dist + 1
       v.pred = u
       Q.enqueue(v)   // add v to back of queue
   Q.dequeue          // pop u off top of queue
   u.color = black

And a bit more Java-ish..

BFS(root) {
  cn = root;

  s.push(cn.getValue()); // Save node value on stack
  cn.setValue(-1); // mark node visited
  q.enqueue(cn);

  while(! q.notEmpty() ) {
    cn = q.dequeue();
    foreach v in cn.getChildren() {
      if (v.getValue() != -1) {
        // This node not visited yet
        s.push(v.getValue()); // save node value on stack
        v.setValue(-1); // mark node visited
        q.enqueue(v);
      }
    }
  }

}

And even simpler..

BFS(root) {
  cn = root;

  cn.visit(); // mark node visited
  q.enqueue(cn);

  while(! q.notEmpty() ) {
    cn = q.dequeue();

    foreach v in cn.getChildren() {
      if ( ! v.visited() ) {
        // This node not visited yet
        v.visit(); // mark node visited
        q.enqueue(v);
      }
    }
  }

}