PHP单链表的反转

图形详解

image.png

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路：

1.定义一个 $pre = null;节点，将当前元素的指针next指向 $pre，同时把当前循环的第一个节点
赋值$pre = $current;

2.利用临时变量$tmp= $current->next;记录节点的走向，处于哪一个位置，当$pre = $current;
赋值成功后，$current= $tmp;表示当前节点下移

3.以此类推，最后$this->head->next = $pre;将当前head头指向新的节点$pre

代码实现

<?php
//---------------------节点类---------------------
class Node
{
    //存储数据
    public $data = '';
    
    //指向下一个节点的地址
    public $next = '';

    public function __construct($data, $next=null)
    {
        $this->data = $data;
        $this->next = $next;
    }
}

//---------------------链表类-单链表---------------------
class SingleLinkedList
{
    //定义头指针
    public $head;

    //链表长度
    public $length;

    //构造方法 用来插入头指针
    public function __construct()
    {
        $this->head = new Node(null);
    }

    //插入
    public function insert($data)
    {
        $current = $this->head;
        while ($current->next !== null) {
            $current = $current->next;
        }
        $current->next = new Node($data);
        $this->length ++;
        return $this;
    }

    //头部插入
    public function headInsert($data)
    {
        $this->head->next = new Node($data,$this->head->next);
        $this->length ++;
        return $this;
    }

    //链表反转
    public function reverse()
    {
        //判断链表的长度是否为0
        if($this->length == 0) {
            return false;
        }
        // 从第一个元素开始遍历
        $current = $this->head->next;
        $pre = null;

        //终止条件---直到元素为NULL
        while ($current !== null) {
            //临时变量 记录操作到哪一个节点
            $tmp = $current->next;

            // 将当前节点的next指向上一个元素(如果是第一个指向NULL)
            $current->next = $pre;

            // 保存当前节点信息, 为下一个元素指向使用
            $pre = $current;

            //当前元素往下移动
            $current = $tmp;
        }

        // 更新头节点指向最后一个元素
        $this->head->next = $pre;
    }
}

//----------------------操作链表--------------------
$linkedList = new SingleLinkedList();
$linkedList->insert(2);
$linkedList->insert(1);
$linkedList->headInsert(3);
$linkedList->reverse();
print_r($linkedList);

参考