札记之PHP实现链表反转

示例 1：
输入：[1,2,3,4,5]
返回的结点值为 [5,4,3,2,1]

代码实现

class ListNode
{
    private $data;
    private $next;
    public function __construct(string $data)
    {
        $this->data = $data;
    }
    public function __get($var)
    {
        return $this->$var;
    }
    public function __set($var, $val)
    {
        return $this->$var = $val;
    }
}

class LinkedList
{
    private $head = NULL;
    private $length = 0;
    private $currentNode;

    public function insert($data = NULL)
    {
        $newNode = new ListNode($data);
        if ($this->head === NULL) {
            $this->head = &$newNode;
        } else {
            $currentNode = $this->head;
            while ($currentNode->next !== NULL) {
                $currentNode = $currentNode->next;
            }
            $currentNode->next = $newNode;
        }
        $this->length++;
        return true;
    }

    public function getList()
    {
        return $this->head;
    }

    public function setList($head)
    {
        $this->head = $head;
    }

    public function reverse()
    {
        if ($this->head == NULL || $this->head->next == NULL) {
            return $this->head;
        }

        $reverseList = NULL;
        $next = NULL;
        $currentNode = $this->head;
        while ($currentNode !== NULL) {
            $next = $currentNode->next;//保存后面链表数据

            $currentNode->next = $reverseList;//将当前节点的下一节点置为前节点  
            $reverseList = $currentNode;//将当前节点保存为前一节点

            $currentNode = $next;//将当前节点置为下一节点
        }
        $this->head = $reverseList;
    }

    //递归
    function reverseList($head = NULL)
    {
        if ($head == NULL || $head->next == NULL) {
            return $head;
        }
        $res = $this->reverseList($head->next);
        $head->next->next = $head;
        $head->next = NULL;
        return $res;
    }

    public function display()
    {
        echo 'LinkList length: ' . $this->length . PHP_EOL;
        $currentNode = $this->head;
        while ($currentNode !== NULL) {
            echo $currentNode->data . PHP_EOL;
            $currentNode = $currentNode->next;
        }
    }
}

$linkedObj = new LinkedList();

$linkedObj->insert(1);
$linkedObj->insert(2);
$linkedObj->insert(3);
$linkedObj->insert(4);
$linkedObj->insert(5);

$head = $linkedObj->getList();
$newHead = $linkedObj->reverseList($head);
$linkedObj->setList($newHead);
$linkedObj->display();

递推

1 2 3 4 5
$next = [2, 3, 4, 5];
$currentNode->next = null;
$reverseList = 1;
$currentNode = $next = [2, 3, 4, 5]

$next = [3, 4, 5];
$currentNode->next = [1];
$reverseList = [2, 1]
$currentNode = $next = [3, 4, 5]

$next = [4, 5];
$currentNode->next = [2, 1];
$reverseList = [3, 2, 1]
$currentNode = $next = [4, 5]

$next = [5];
$currentNode->next = [3, 2, 1];
$reverseList = [4, 3, 2, 1]
$currentNode = $next = [5]

$reverseList = [5, 4, 3, 2, 1]

运行结果

5
4
3
2
1