链表翻转循环和递归写法(画图分析)

class Node
{
    public $e;//节点元素
    public $next; //下个节点信息
    /**
     * 构造函数 设置节点信息
     * Node constructor.
     * @param $e
     * @param $next
     */
    public function __construct($e, $next=null)
    {
        $this->e = $e;
        $this->next = $next;
    }
}

<?php
require 'LinkedList.php';
$linkedList = new LinkedList();
for ($i = 1;$i <= 20;$i++){
    $linkedList->addFirst($i);
}
echo $linkedList->toString();
/**
 * 20->19->18->17->16->15->14->13->12->11->10->9->8->7->6->5->4->3->2->1->null
 */
echo "\n";
function reverse($head){
    $pre = $head;
    $cur = $head->next;
    while ($cur){
        $next = $cur->next;
        $cur->next = $pre;
        $pre = $cur;
        $cur = $next;
    }
    $head->next = null;
    return $pre;
}
$linkedList->setHead(reverse($linkedList->getHead()));
echo $linkedList->toString();
/**
 * 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->null
 */
echo "\n";

public function recursionLinkedList(){
        $this->head = $this->recursion($this->head);
    }
    private function recursion($head){
        if($head->next == null){
            return $head;
        }
        $cur = $head;
        $next = $this->recursion($head->next);//这个想象成一个已经翻转的链表其返回值是头
        $head->next->next = $head;//需要得到递归整体链表的尾部，有一种low办法就是遍历，但在这里可以直接取 $head节点的 next 节点，因为其指向的地址没有变
        $head->next = null;//原来的头需要指向null
        return $next;//最后需要返回递归整体这个链表
    }