Reverse a Linked List, Java

2009/10/09

Reviewing for interview questions, I ran across this. Most solutions you’ll find are in C, and that can be easily adapted … however, the C-ness sometimes gets in the way of spotting the subtleties. Here is the function in Java,

static void Node reverse(Node head) {
Node current = head;
Node newHead = null;
while (current != null) {
Node tmp = current;
current = current.next;
tmp.next = newHead;
newHead = tmp;
}
return newHead;
}

So how does it work? In a nutshell, we always have 2 lists: 1) the remaining portion of the original list pointed to by current, and 2) the new list pointed to by newHead. Each iteration strips the head element from the original list, and adds it to the head of the new list.

  • line 5 saves the current loop pointer, this will be our new head at the end of each loop.
  • line 6 advances the current loop pointer one past the head, but remember we saved the old current pointer in tmp at line 5.
  • line 7 assigns the next pointer of our new head (tmp) to the previous head pointer. The first time through the loop, this is null, and we’ll have a new list containing one item.
  • line 8 permanently tracks our new head by moving it out of the temporary loop var.

I can’t imagine it gets better than this. No new allocations, and O(n).

Advertisements

CraigsHome – Android App

2009/09/26

device-1

iconI published a new Android application to the market today: CraigsHome. CraigsHome plots CraigsList rental listings on your Google map. You can get more information about the listing including photos, and even email the author right from your device with one click.

Right now, it only covers rentals (apartment, room, house). It could easily also cover for sale listings. Without going into too many details, it would require some extra processing on the back side. With for sale listings, this could be the Zillow-killer app. Re-presenting data from CL is never going to be as clean as Zillow listings, but with the popularity (and free-ness) of CL, it could really put a dent in things for them.

device-3device-2