reverse-linked-list.js

#!/usr/bin/env node
var util = require( "util" );

// Create a linked-list and reverse it.
// This is just a rough bit of code to solve the problem.
// If I had more time I would maybe try a different algorithm
// where I switch the pointer as I walk to the end.
// Also I may change the members to be private.

util.puts( "Make a list and print it out!" );

// --------------------------------------
// Make a Node class for the linked list.
// --------------------------------------
var Node = function(obj) {
	this.thing = obj;
	this.pointer = null;
};
Node.newFirst = null;
Node.prototype.print = function() {
	util.puts(this.thing + " -> " + ((this.pointer === null) ? "null" : this.pointer.thing));
	if (this.pointer !== null) {
		this.pointer.print();
	}
};
// Implement a recursive function that walks to the end
// and reverses each pointer on the way back to the beginning.
// The last shall be first.
Node.prototype.reverse = function() {
	Node.newFirst = null;
	this.reverseInner(null);
	return Node.newFirst;
}
Node.prototype.reverseInner = function(prevNode) {
	if (this.pointer === null) {
		Node.newFirst = this;
	} else {
		this.pointer.reverseInner(this);
	}
	this.pointer = prevNode;
};
Node.prototype.attach = function(node) {
	this.pointer = node;
	return this.pointer;
};
// --------------------------------------
// End Node class
// --------------------------------------

// Create a few nodes.
var node1 = new Node(2);
var node2 = new Node(4);
var node3 = new Node(6);

// Attach the nodes together with chaining.
node1.attach(node2).attach(node3).attach(new Node(8));

// print the nodes before reversing them.
node1.print();

util.puts( "Reverse the list!" );

reversedList = node1.reverse();
reversedList.print();