PHP翻转一个单向链表（图解）

2019-03-14

字数统计: 481 | 阅读时长≈ 2 分钟

最近在撸mysql发现底层很多涉及到数据结构和算法的知识点，看见有点撸不动了转过头来看算法。

链表是什么

链表与动态链表这个里面有用C完成的一部分介绍，知识刚好可以交叉。其实单这样看也是看不动的推荐我的docker环境，和打开PHP的xdebug

#完整代码实现

<?php

/**
 * 一个链表结构
 * Class ListNode
 */
class ListNode {
    public $val = 0;
    public $next = null;

    function __construct($val)
    {
        $this->val = $val;
    }
}

/**
 * 链表尾部追加
 * @param $node
 * @param $val
 */
function addList($header ,$val)
{
    $scan = $header;

    while(!is_null($scan->next)){
        $scan = $scan->next;//遍历到尾部
    }

    $scan->next =  new ListNode($val);

}

/**
 * 打印这个链表
 * @param $header
 */
function seeList($header)
{
    $scan = $header;
    while(!is_null($scan->next)){
        echo $scan->val.PHP_EOL;
        $scan = $scan->next;
    }
    echo $scan->val.PHP_EOL;
}

/**
 * 反转
 * @param $header
 * @return string
 */
function rev($header)
{

    $re = '';

    while($header){
        $temp = $header->next;
        $header->next = $re;
        $re = $header;
        $header = $temp;

    }

    return $re;

}


$header = new ListNode(1);
addList($header ,2);
addList($header ,3);
addList($header ,4);
seeList(rev($header));