Reversing a linked list in a specific manner through PHP

Question

Given a Singly Linked List $link, with elements (a->b->c->d->e->f->g->h->i->j), we need to reverse the linked list provided that the reversing will be done in a manner like -

Reverse 1st element (a)

Reverse next 2 elements (a->c->b)

Reverse next 3 elements (a->c->b->f->e->d)

Reverse next 4 elements (a->c->b->f->e->d->j->i->h->g)

....

....

I am looking for a PHP function code which takes the linked list $link and reverse it in above manner with least time complexity.

For help, I am adding my code below for linked list. The function reverseLinkedList has to be completed to perform this specific reverse operation -

class ListNode
{
    public $data;
    public $next;

    function __construct($data)
    {
        $this->data = $data;
        $this->next = NULL;
    }

    function read_node()
    {
        return $this->data;
    }
}

class LinkList
{
    private $first_node;
    private $last_node;
    private $count;

    function __construct()
    {
        $this->first_node = NULL;
        $this->last_node = NULL;
        $this->count = 0;
    }

    function size()
    {
        return $this->count;
    }

    public function read_list()
    {
        $listData = array();
        $current = $this->first_node;
        while($current != NULL)
        {
            echo $current->read_node().' ';
            $current = $current->next;
        }
    }

    public function reverse_list()
    {
        if(($this->first_node != NULL)&&($this->first_node->next != NULL))
        {
            $current = $this->first_node;
            $new = NULL;

            while ($current != NULL)
            {
                $temp = $current->next;
                $current->next = $new;
                $new = $current;
                $current = $temp;
            }
            $this->first_node = $new;
        }
    }

    public function read_node($position)
    {
        if($position <= $this->count)
        {
            $current = $this->first_node;
            $pos = 1;
            while($pos != $position)
            {
                if($current->next == NULL)
                    return null;
                else
                    $current = $current->next;

                $pos++;
            }
            return $current->data;
        }
        else
            return NULL;
    }

    public function insert($data)
    {
        $new_node = new ListNode($data);

        if($this->first_node != NULL)
        {
            $this->last_node->next = $new_node;
            $new_node->next = NULL;
            $this->last_node = &$new_node;
            $this->count++;
        }
        else
        {
            $new_node->next = $this->first_node;
            $this->first_node = &$new_node;

            if($this->last_node == NULL)
                $this->last_node = &$new_node;

            $this->count++;
        }
    }
}


//Create linked list
$link1 = new LinkList();

//Insert elements
$link1->insert('a');
$link1->insert('b');
$link1->insert('c');
$link1->insert('d');
$link1->insert('e'); 
$link1->insert('f'); 
$link1->insert('g'); 
$link1->insert('h');
$link1->insert('i'); 
$link1->insert('j'); 

echo "<b>Input :</b><br>";       
$link1->read_list();


//function to reverse linked list in specified manner
function reverseLinkedList(&$link1)
{
  //Logic to reverse the linked list $link1
}
///function to reverse linked list in specified manner

//Reverse current linked list $link1
reverseLinkedList($link1);

echo "<br><br><b>Output :</b><br>";       
$link1->read_list();

Answer 1

For example You have linked objects:

class obj {
    public $next;
}

$a = new obj();
$b = new obj();
$c = new obj();
$d = new obj();

$a->next = $b;
$b->next = $c;
$c->next = $d;
$d->next = null;

$obj = $a;

Your task is to make sure that the result is returned in the reverse sequence:

$d->next->$c->next->$b->next->$a = null;

Try to use the following code for yourself and fix it for your task

$new = null;

function recursive(&$new, &$obj) {

    if(is_object($new) && (spl_object_id($new)-1) === 0) {
        return null;
    }

    $getLast = function (&$obj) use(&$getLast) {
        if($obj->next === null) {
            return $obj;
        }

        return $getLast($obj->next);
    };

    $dropLast = function (&$obj) use(&$dropLast) {

        if(!isset($obj->next)) {
            return null;
        }

        if($obj->next->next === null) {
            $obj->next = null;
            return null;
        }

        return $dropLast($obj->next);
    };

    if($new === null) {
        $new = $getLast($obj);
        $dropLast($obj);
        $new->next = $getLast($obj);
    } else {
        $new->next = $getLast($obj);
    }

    $dropLast($obj);

    return recursive($new->next, $obj);
}

recursive($new, $obj);

echo '<pre>';
var_dump($new);
exit;