Archive for December, 2009

 

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

Dec 27, 2009 in Algorithms, Java

From http://www.java2blog.com/2014/07/how-to-reverse-linked-list-in-java.html

[java]

public void reverse(ListNode head) {
ListNode curr = head;
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;
}

[/java]

Recursive method:

[java]
public ListNode reverseList(ListNode head) {
// from: http://www.java2blog.com/2014/07/how-to-reverse-linked-list-in-java.html
if ( head == null || head.next == null )
return head;

ListNode rlist = reverseList(head.next);
head.next.next = head;
head.next = null;

return rlist;
}
[/java]

. . .

Breadth first search traversal algorithm..

Dec 02, 2009 in Algorithms, Java

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..

[java]

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);
}
}
}

}

[/java]

And even simpler..

[java]

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);
}
}
}

}

[/java]