php 实现单链表以及链表反转等操作

class SingleLinkedListNode{    /**     * 节点中的数据域     *     * @var null     */    public $data;
    /**     * 节点中的指针域，指向下一个节点     *     * @var SingleLinkedListNode     */    public $next;
    /**     * SingleLinkedListNode constructor.     *     * @param null $data     */    public function __construct($data = null)    {        $this->data = $data;        $this->next = null;    }}

class SingleLinkedList{    /**     * 单链表头结点（哨兵节点）     *     * @var SingleLinkedListNode     */    public $head;
    /**     * 单链表长度     *     * @var     */    private $length;
    /**     * 初始化单链表     *     * SingleLinkedList constructor.     *     * @param null $head     */    public function __construct($head = null)    {        if (null == $head) {            $this->head = new SingleLinkedListNode();        } else {            $this->head = $head;        }
        $this->length = 0;    }
    /**     * 获取链表长度     *     * @return int     */    public function getLength()    {        return $this->length;    }
    /**     * 插入数据 采用头插法 插入新数据     *     * @param $data     *     * @return SingleLinkedListNode|bool     */    public function insert($data)    {        return $this->insertDataAfter($this->head, $data);    }
    /**     * 删除节点     *     * @param SingleLinkedListNode $node     *     * @return bool     */    public function delete(SingleLinkedListNode $node)    {        if (null == $node) {            return false;        }
        // 获取待删除节点的前置节点        $preNode = $this->getPreNode($node);        if (empty($preNode)) {            return false;        }
        // 修改指针指向        $preNode->next = $node->next;        unset($node);
        $this->length--;        return true;    }
    /**     * 通过索引获取节点     *     * @param int $index     *     * @return SingleLinkedListNode|null     */    public function getNodeByIndex($index)    {        if ($index >= $this->length) {            return null;        }
        $cur = $this->head->next;        for ($i = 0; $i < $index; ++$i) {            $cur = $cur->next;        }
        return $cur;    }
    /**     * 获取某个节点的前置节点     *     * @param SingleLinkedListNode $node     *     * @return SingleLinkedListNode|bool|null     */    public function getPreNode(SingleLinkedListNode $node)    {        if (null == $node) {            return false;        }
        $curNode = $this->head;        $preNode = $this->head;        // 遍历找到前置节点 要用全等判断是否是同一个对象        // http://php.net/manual/zh/language.oop5.object-comparison.php        while ($curNode !== $node) {            if ($curNode == null) {                return null;            }            $preNode = $curNode;            $curNode = $curNode->next;        }
        return $preNode;    }
    /**     * 输出单链表 当data的数据为可输出类型     *     * @return bool     */    public function printList()    {        if (null == $this->head->next) {            return false;        }
        $curNode = $this->head;        // 防止链表带环，控制遍历次数        $listLength = $this->getLength();        while ($curNode->next != null && $listLength--) {            echo $curNode->next->data . ' -> ';
            $curNode = $curNode->next;        }        echo 'NULL' . PHP_EOL;
        return true;    }
    /**     * 输出单链表 当data的数据为可输出类型     *     * @return bool     */    public function printListSimple()    {        if (null == $this->head->next) {            return false;        }
        $curNode = $this->head;        while ($curNode->next != null) {            echo $curNode->next->data . ' -> ';
            $curNode = $curNode->next;        }        echo 'NULL' . PHP_EOL;
        return true;    }
    /**     * 在某个节点后插入新的节点 (直接插入数据)     *     * @param SingleLinkedListNode $originNode     * @param                      $data     *     * @return SingleLinkedListNode|bool     */    public function insertDataAfter(SingleLinkedListNode $originNode, $data)    {        // 如果originNode为空，插入失败        if (null == $originNode) {            return false;        }
        // 新建单链表节点        $newNode = new SingleLinkedListNode();        // 新节点的数据        $newNode->data = $data;
        // 新节点的下一个节点为源节点的下一个节点        $newNode->next = $originNode->next;        // 在originNode后插入newNode        $originNode->next = $newNode;
        // 链表长度++        $this->length++;
        return $newNode;    }
    /**     * 在某个节点前插入新的节点（很少使用）     *     * @param SingleLinkedListNode $originNode     * @param                      $data     *     * @return SingleLinkedListNode|bool     */    public function insertDataBefore(SingleLinkedListNode $originNode, $data)    {        // 如果originNode为空，插入失败        if (null == $originNode) {            return false;        }
        // 先找到originNode的前置节点，然后通过insertDataAfter插入        $preNode = $this->getPreNode($originNode);
        return $this->insertDataAfter($preNode, $data);    }
    /**     * 在某个节点后插入新的节点     *     * @param SingleLinkedListNode $originNode     * @param SingleLinkedListNode $node     *     * @return SingleLinkedListNode|bool     */    public function insertNodeAfter(SingleLinkedListNode $originNode, SingleLinkedListNode $node)    {        // 如果originNode为空，插入失败        if (null == $originNode) {            return false;        }
        $node->next = $originNode->next;        $originNode->next = $node;
        $this->length++;
        return $node;    }
    /**     * 构造一个有环的链表     */    public function buildHasCircleList()    {        $data = [1, 2, 3, 4, 5, 6, 7, 8];
        $node0 = new SingleLinkedListNode($data[0]);        $node1 = new SingleLinkedListNode($data[1]);        $node2 = new SingleLinkedListNode($data[2]);        $node3 = new SingleLinkedListNode($data[3]);        $node4 = new SingleLinkedListNode($data[4]);        $node5 = new SingleLinkedListNode($data[5]);        $node6 = new SingleLinkedListNode($data[6]);        $node7 = new SingleLinkedListNode($data[7]);
        $this->insertNodeAfter($this->head, $node0);        $this->insertNodeAfter($node0, $node1);        $this->insertNodeAfter($node1, $node2);        $this->insertNodeAfter($node2, $node3);        $this->insertNodeAfter($node3, $node4);        $this->insertNodeAfter($node4, $node5);        $this->insertNodeAfter($node5, $node6);        $this->insertNodeAfter($node6, $node7);
        $node7->next = $node4;    }}

class SingleLinkedListTool{    /**     * 单链表     *     * @var     */    public $list;
    /**     * 构造函数设置$list     *     * SingleLinkedListAlgo constructor.     *     * @param SingleLinkedList $list     */    public function __construct(SingleLinkedList $list = null)    {        $this->list = $list;    }
    /**     * 设置单链表     *     * @param SingleLinkedList $list     */    public function setList(SingleLinkedList $list)    {        $this->list = $list;    }
    /**     * 单链表反转     *     * 三个指针反转     * preNode 指向前一个结点     * curNode 指向当前结点     * remainNode 指向当前结点的下一个节点（保存未逆序的链表，为了在断开curNode的next指针后能找到后续节点）     *     * @return bool     */    public function reverse()    {        if (null == $this->list || null == $this->list->head || null == $this->list->head->next) {            return false;        }
        $preNode = null;        $curNode = $this->list->head->next;        $remainNode = null;
        // 保存头结点，稍后指向反转后的链表        $headNode = $this->list->head;        // 断开头结点的next指针        $this->list->head->next = null;
        while ($curNode != null) {            $remainNode = $curNode->next;            $curNode->next = $preNode;            $preNode = $curNode;            $curNode = $remainNode;        }
        // 头结点指向反转后的链表        $headNode->next = $preNode;
        return true;    }
    /**     * 判断链表是否有环     *     * 快慢指针判断是否有环     *     * @return bool     */    public function checkCircle()    {        if (null == $this->list || null == $this->list->head || null == $this->list->head->next) {            return false;        }
        $slow = $this->list->head->next;        $fast = $this->list->head->next;
        while ($fast != null && $fast->next != null) {            $fast = $fast->next->next;            $slow = $slow->next;
            // 如果慢指针跟快指针相遇了说明有环            if ($slow === $fast) {                return true;            }        }
        return false;    }
    /**     * 合并两个有序链表     *     * @param SingleLinkedList $listA     * @param SingleLinkedList $listB     *     * @return SingleLinkedList|SingleLinkedListNode     */    public function mergerSortedList(SingleLinkedList $listA, SingleLinkedList $listB)    {        if (null == $listA) {            return $listB;        }        if (null == $listB) {            return $listA;        }
        $pListA = $listA->head->next;        $pListB = $listB->head->next;        $newList = new SingleLinkedList();        $newHead = $newList->head;        $newRootNode = $newHead;
        while ($pListA != null && $pListB != null) {            if ($pListA->data <= $pListB->data) {                $newRootNode->next = $pListA;                $pListA = $pListA->next;            } else {                $newRootNode->next = $pListB;                $pListB = $pListB->next;            }            $newRootNode = $newRootNode->next;        }
        // 如果第一个链表未处理完，拼接到新链表后面        if ($pListA != null) {            $newRootNode->next = $pListA;        }        // 如果第二个链表未处理完，拼接到新链表后面        if ($pListB != null) {            $newRootNode->next = $pListB;        }
        return $newList;    }
    /**     * 删除链表倒数第n个结点     *     * @param $index     *     * @return bool     */    public function deleteLastKth($index)    {        if (null == $this->list || null == $this->list->head || null == $this->list->head->next) {            return false;        }
        $i = 1;        $slow = $this->list->head;        $fast = $this->list->head;        while ($fast != null && $i < $index) {            $fast = $fast->next;            ++$i;        }
        if (null == $fast) {            return true;        }
        $pre = null;        while ($fast->next != null) {            $pre = $slow;            $slow = $slow->next;            $fast = $fast->next;        }
        if (null == $pre) {            $this->list->head->next = $slow->next;        } else {            $pre->next = $pre->next->next;        }
        return true;    }
    /**     * 寻找中间节点     *     * 快慢指针遍历     *     * @return SingleLinkedListNode|bool|null     */    public function findMiddleNode()    {        if (null == $this->list || null == $this->list->head || null == $this->list->head->next) {            return false;        }
        $slow = $this->list->head->next;        $fast = $this->list->head->next;
        while ($fast != null && $fast->next != null) {            $fast = $fast->next->next;            $slow = $slow->next;        }
        return $slow;    }
    /**     * 检查是否回文     * @return bool     */    public function isPalindrome()    {        if ($this->list->getLength() <= 1) {            return true;        }
        $pre = null;        $slow = $this->list->head->next;        $fast = $this->list->head->next;        $remainNode = null;
        // 找单链表中点 以及 反转前半部分链表        while ($fast != null && $fast->next != null) {            $fast = $fast->next->next;
            // 单链表反转关键代码 三个指针            $remainNode = $slow->next;            $slow->next = $pre;            $pre = $slow;            $slow = $remainNode;        }        // 链表长度为偶数的情况        if ($fast != null) {            $slow = $slow->next;        }
        // 开始逐个比较        while ($slow != null) {            if ($slow->data != $pre->data) {                return false;            }            $slow = $slow->next;            $pre = $pre->next;        }        return true;    }}