Leetcode之PHP版题目解析(234. Palindrome Linked List)

2019-4-3 期三  

 Leetcode之PHP版题目解析(232. Implement Queue using Stacks)

3b30bfb3f38a8f6f6ab821f3c02b831e.png

给你一个单链表,判断是不是回文链表,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 是一个回文链表

按照我们的逻辑,此时栈顶是2,栈底是1,此时的结点就在链表的最中间,当前节点不需要去进行比较,只需要比较它的左右两侧是否相等即可.

 另外,题目的要求是0(n)的时间复杂度,O(1)的空间复杂度,这里定义了一个数组存储,空间已经是O(n)了,需要改进.安排一下??

吴亲库里 has written 35 articles

情绪只是对自己无能的愤怒

积分:1817 等级:P6 职业:php 城市:杭州

0 条回复

登录后才能进行评论,立即登录?