Leetcode之PHP版题目解析（234. Palindrome Linked List）

2019-4-3 星期三  开始吧

上一题链接 Leetcode之PHP版题目解析（232. Implement Queue using Stacks）

题目描述

给你一个单链表,判断是不是回文链表,Leetcode关于回文的题目很多的,第九题就是判断回文数,去年Leetcode还不支持php,我用的js写的,明天改一下放出来.

题目分析

我的思路定义两个指针(快慢),再定义一个栈这样的数据结构(为什么用栈呢),原理就是每次慢指针走一步,我都把当前结点的值压入栈,等快指针走完链表的时候我们已经把链表的前半部分存入栈中了,只要把链表的前半部分和后半部分做比较(利用栈后进先出特点),如果都相等就表明是回文链表了.

具体实现

      /**
     * @param ListNode $head
     * @return Boolean
     */
    function isPalindrome($head) {

        if(!$head || !$head->next){
            return true;
        }
        $slow=$head;
        $fast=$head;
        $stack=[];
        array_unshift($stack,$head->val);
        while($fast->next && $fast->next->next) {
            $slow=$slow->next;
            $fast=$fast->next->next;
            array_unshift($stack,$slow->val);
        }
        if(!$fast->next) array_shift($stack);
        while($slow->next) {
            $slow=$slow->next;
            $val=array_shift($stack);
            if($slow->val !== $val){
                return false;
            }
        }
        
        return true; 
    }

这里还有一个点

     if(!$fast->next) array_shift($stack); //举个例子 当前链表是 1->2->1 是一个回文链表