圖形詳解

image.png

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

思路：

1.定義一個 $pre = null;節(jié)點，將當(dāng)前元素的指針next指向 $pre，同時把當(dāng)前循環(huán)的第一個節(jié)點
賦值$pre = $current;

2.利用臨時變量$tmp= $current->next;記錄節(jié)點的走向，處于哪一個位置，當(dāng)$pre = $current;
賦值成功后，$current= $tmp;表示當(dāng)前節(jié)點下移

3.以此類推，最后$this->head->next = $pre;將當(dāng)前head頭指向新的節(jié)點$pre

代碼實現(xiàn)

<?php
//---------------------節(jié)點類---------------------
class Node
{
    //存儲數(shù)據(jù)
    public $data = '';
    
    //指向下一個節(jié)點的地址
    public $next = '';

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

//---------------------鏈表類-單鏈表---------------------
class SingleLinkedList
{
    //定義頭指針
    public $head;

    //鏈表長度
    public $length;

    //構(gòu)造方法 用來插入頭指針
    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;
    }

    //鏈表反轉(zhuǎn)
    public function reverse()
    {
        //判斷鏈表的長度是否為0
        if($this->length == 0) {
            return false;
        }
        // 從第一個元素開始遍歷
        $current = $this->head->next;
        $pre = null;

        //終止條件---直到元素為NULL
        while ($current !== null) {
            //臨時變量 記錄操作到哪一個節(jié)點
            $tmp = $current->next;

            // 將當(dāng)前節(jié)點的next指向上一個元素(如果是第一個指向NULL)
            $current->next = $pre;

            // 保存當(dāng)前節(jié)點信息, 為下一個元素指向使用
            $pre = $current;

            //當(dāng)前元素往下移動
            $current = $tmp;
        }

        // 更新頭節(jié)點指向最后一個元素
        $this->head->next = $pre;
    }
}

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

參考