醉丶春风的Blog

千里之行, 始于足下



php判断是否回文链表


回文字符串

当一个字符串正着读反着读都一样的时候, 代表它是一个回文字符串,如:

  • 121: true
  • aaa: true
  • abb: false
  • abba: true

功能分析

使用单链表实现一个功能,给定一个字符串, 返回是否回文

前面已经说了链表反转和快慢指针的应用, 此处就同时使用了链表反转和快慢指针
步骤如下:

  1. 使用快慢指针法,遍历链表, 得到链表中位数,此时遍历了length/2长度
  2. 将链表中位数后面的元素反转
  3. 从头比较链表和反转后的链表,如果有不相同的元素, 则不是回文,如果反转的后半部分链表走到了终点, 则为回文链表

例子:

  1. 给定 1->2->3->2->1, 第一步得到中位数3, 反转后半部分等到 1->2, 两个链表相比较
  2. 给定 a->b->c->c->b->a, 第一步得到中位数c, 反转后半部分等到 a->b->c, 两个链表相比较

通过上面的例子发现, 此处不用区分是奇数链表还是偶数链表

图片演示

alt

代码实现

链表节点类

class Node {

    public $data;

    /**
     * @var self
     */
    public $next = null;

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

链表类

class LinkedList {

    /**
     * @var Node
     */
    public $head;

    public function __construct()
    {
        $this->head = new Node();
    }

    public function clear()
    {
        $this->head->next = null;
    }

    public function insert($data)
    {
        $current = $this->head;

        while ($current->next !== null) {
            $current = $current->next;
        }

        $current->next = new Node($data);

        return $this;
    }

    public function getLength()
    {
        $length = 0;
        $current = $this->head->next;
        while ($current !== null) {
            $current = $current->next;
            $length ++;
        }

        return $length;
    }

    public function printAll()
    {
        echo '<hr>';
        $current = $this->head->next;
        while ($current !== null) {
            echo $current->data;
            echo '<br>';
            $current = $current->next;
        }
    }

    public function setString($string)
    {
        $this->clear();
        $current = $this->head;
        for ($i=0; $i<strlen($string); $i++) {
            $current->next = new Node($string[$i]);
            $current = $current->next;
        }
        return $this;
    }

    /**
     * 判断是否回文链表
     * @return bool
     */
    public function isPalindrome()
    {
        $fast = $this->head;
        $slow = $this->head;

        // 通过快慢指针, 查找到链表中位数
        while ($fast !== null && $fast->next !== null) {
            $fast = $fast->next->next;
            $slow = $slow->next;
        }

        // 返回中位数后面的元素
        $prev = null;
        $tmpCurrent = $slow->next;
        while ($tmpCurrent !== null) {
            $next = $tmpCurrent->next;
            $tmpCurrent->next = $prev;
            $prev = $tmpCurrent;
            $tmpCurrent = $next;
        }

        $slow = $prev;
        $fast = $this->head->next;

        // 遍历比较
        while ($slow !== null) {
            if ($slow->data != $fast->data) {
                return false;
            }
            $fast = $fast->next;
            $slow = $slow->next;
        }
        return true;
    }

}

代码测试

// 判断是否回文字符串
$linkList = new LinkedList();

var_dump($linkList->setString('121')->isPalindrome());
var_dump($linkList->setString('abccba')->isPalindrome());
var_dump($linkList->setString('aaa')->isPalindrome());
var_dump($linkList->setString('abc')->isPalindrome());

作者: 徐善通
地址: https://www.xstnet.com/article-119.html
声明: 除非本文有注明出处,否则转载请注明本文地址


我有话说



最新回复


正在加载中....

Copyrights © 2016-2019 醉丶春风 , All rights reserved. 皖ICP备15015582号-1