Reverse List

reverseList.php

<?php

class Node{
	public $id, $next;

	public function __construct($id,$next){
		$this->id = $id;
		$this->next = $next;
	}
}

function reverseLinkedList($cursor){
	$prev = $next = null;
	while($cursor->next !== null){
		$next = $cursor->next;
		$cursor->next = $prev;
		$prev = $cursor;
		$cursor = $next;
	}
	//set last node to null
	$cursor->next = $prev;
	return $cursor;
}

function recuriveReverse($cursor){
	//gives us that last element to be our new head.
	if($cursor->next == null)
		return $cursor;

	//first element must point to null
	$next = $cursor->next;
	$cursor->next = null;

	//free to reverse the rest of the list
	$newHead = recuriveReverse($next);
	//reversing the pointer.
	$next->next = $cursor;

	return $newHead;
}


function printOutLinkedList($head){
	do{
		echo $head->id . "->";
	}while($head = $head->next);
	echo "<br/>";
}

$nodes = new Node("1", new Node("2",new Node("3", new Node("4",null))));
printOutLinkedList($nodes);
printOutLinkedList(reverseLinkedList($nodes));


$nodes = new Node("1", new Node("2",new Node("3", new Node("4",null))));
printOutLinkedList($nodes);
printOutLinkedList(recuriveReverse($nodes));

?>