醉丶春风的Blog

回文字符串

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

• 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, 两个链表相比较

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

图片演示

代码实现

链表节点类

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());