文章目录
-
-
- 链表翻转循环和递归写法
- 1.链表翻转循环实现原理图
- 2.节点定义
- 3.链表翻转循环实现代码
- 4.链表翻转递归实现思想步骤和原理图
- 5.递归代码
-
链表翻转循环和递归写法
1.链表翻转循环实现原理图
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHLw0kaONTTU9ENNpHW4Z0MMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLzcjNxMzNxAjM5ATMwEjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
2.节点定义
class Node
{
public $e;//节点元素
public $next; //下个节点信息
/**
* 构造函数 设置节点信息
* Node constructor.
* @param $e
* @param $next
*/
public function __construct($e, $next=null)
{
$this->e = $e;
$this->next = $next;
}
}
3.链表翻转循环实现代码
<?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";
演示输出如下图:
4.链表翻转递归实现思想步骤和原理图
- 画图分析
- 将递归函数当成整体,不要跳进递归里边(因为你的脑袋压栈不了几个)
- 写代码先处理递归到底的情况
链表翻转循环和递归写法
5.递归代码
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;//最后需要返回递归整体这个链表
}
演示输出如下图:
Tips:代码仓库:、
https://gitee.com/love-for-poetry/arithmetic
。
https://gitee.com/love-for-poetry/data-structure
扫码关注