## Archive for December, 2009

### Reversing a singly-linked list in Java .. iterative and recursive methods ..

Dec 27, 2009 in Algorithms, Java

```
ListNode prev = null;
ListNode next = null;

while (curr != null) {
next = curr.next;
curr.next = prev; // reverse link to previous
prev = curr;
curr = next;
}

return prev;
}

```

Recursive method:

```public ListNode reverseList(ListNode head) {

return rlist;
}
```

. . .

### Breadth first search traversal algorithm..

Dec 02, 2009 in Algorithms, Java

```
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.isEmpty() ) {
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.isEmpty() ) {
cn = q.dequeue();

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

}

```