coding for interviews 2013 01 03, PHP solution

linkedlist.php

<?php

class Slist {
        var $data = NULL;
        var $next = NULL;
        
        function __construct($data, $next) {
                $this->data = $data;
                $this->next = $next;
        }
        
        // changes the next pointers to reverse the order of nodes in the list
        // for a lasso, only the loop is reversed
        static function reverse($slist) {
                $prev = NULL;
                while($slist !== NULL) {
                        $temp = $slist->next;
                        $slist->next = $prev;
                        $prev = $slist;
                        $slist = $temp;
                }
                return $prev;
        }

        static function _reverse_rec($slist, $prev) {
                if($slist === NULL)
                        return $prev;
                $next = $slist->next;
                $slist->next = $prev;
                return self::_reverse_rec($next, $slist);
        }

        static function reverse_rec($slist) {
                return self::_reverse_rec($slist, NULL);
        }

        // slurps values from array into a Slist with the same traversal order
        static function from_array($array) {
                $array = array_reverse($array);
                $slist = NULL;
                foreach($array as $value) {
                        $slist = new Slist($value, $slist);
                }
                return $slist;
        }

        // dump values from Slist into array with same traversal order
        // will fail for lassos
        static function to_array($slist) {
                $array = array();
                while($slist !== NULL) {
                        $array[] = $slist->data;
                        $slist = $slist->next;
                }
                return $array;
        }

        // true if list is nonempty and no node in this list has a next of NULL O(N)
        static function has_loop($slist) {
                if($slist === NULL || $slist->next === NULL)
                        return FALSE;
                $reversed = self::reverse($slist);
                $loop = $reversed === $slist;
                self::reverse($reversed);
                return $loop;
        }

        // concatenate two Slists
        // prefix must not have a loop
        static function concat($prefix, $suffix) {
                if($prefix === NULL)
                        return $suffix;
                $tail = $prefix;
                while($tail->next !== NULL) {
                        $tail = $tail->next;
                }
                $tail->next = $suffix;
                return $prefix;
        }

        // THIS ONE DOESN"T WORK, CLEARLY
        static function remove_nfromlast($slist, $n) {
                $n++;
                $ring = array_fill(0, $m, NULL);
                while($slist !== NULL) {
                        $ring[$n % $m] = $slist;
                        $slist = $slist->next;
                        ++$n;
                }
        }

        // destructively de-dups adjacent nodes with === data
        static function uniq($slist) {
                if($slist === NULL || $slist->next === NULL)
                        return $slist;
                $runstart = $slist;
                $rest = $slist->next;
                while($rest !== NULL) {
                        if($rest->data !== $runstart->data) {
                                        $runstart->next = $rest;
                                        $runstart = $rest;
                        }
                        $rest = $rest->next;
                }
                $runstart->next = NULL;
                return $slist;
        }

        // O(NlogN) expected time in-situ sort O(N^2) worst case
        // undefined behavior for lassos
        static function quicksort($slist) {
                // eliminate trivially "sorted" lists
                if($slist === NULL || $slist->next === NULL)
                        return $slist;
                $pivot_node = $slist;
                $rest = $slist->next;
                $slist->next = NULL;
                $lessthan = NULL;
                $atleast = NULL;
                // divide
                while($rest !== NULL) {
                        $next = $rest->next;
                        if($pivot_node->data > $rest->data) {
                                $rest->next = $lessthan;
                                $lessthan = $rest;
                        } else {
                                $rest->next = $atleast;
                                $atleast = $rest;
                        }
                        $rest = $next;
                }
                // conquer
                $lessthan = self::quicksort($lessthan);
                $atleast = self::quicksort($atleast);
                return self::concat($lessthan, self::concat($pivot_node, $atleast));
        }

}

$a = range(1, 25);

$fwd = Slist::from_array($a);
$rev = Slist::reverse($fwd);
echo "REVERSED\n";
echo implode(' ', Slist::to_array($rev)) . "\n";

$fwd = Slist::reverse_rec($rev);
echo "REVERSED AGAIN\n";
echo implode(' ', Slist::to_array($fwd)) . "\n";

echo "SHUFFLED\n";
shuffle($a);
echo implode(' ', $a) . "\n";

$slist = Slist::from_array($a);
$slist = Slist::quicksort($slist);
$b = Slist::to_array($slist);

echo "SORTED\n";
echo implode(' ', $b) . "\n";

echo "HAS LOOP? " . (Slist::has_loop($slist) ?: "works\n");

$x = new Slist(0, NULL);
$x->next = $x;
echo "HAS_LOOP? " . Slist::has_loop($x) . "\n";

$x = new Slist(1, $x);
echo "HAS_LOOP? " . Slist::has_loop($x) . "\n";

$x = Slist::from_array(range(1, 25));
$x = Slist::concat($x, $x);
echo "HAS_LOOP? " . Slist::has_loop($x) . "\n";

$x = Slist::concat(Slist::from_array(range(50,75)), $x);
echo "HAS_LOOP? " . Slist::has_loop($x) . "\n";

$c = array_merge(range(1, 25), range(1, 25, 2));
$l = Slist::from_array($c);
$l = Slist::uniq(Slist::quicksort($l));
echo "UNIQED\n" . implode(' ', Slist::to_array($l)) . "\n";