Skip to content

Latest commit

 

History

History
64 lines (52 loc) · 2.4 KB

234.md

File metadata and controls

64 lines (52 loc) · 2.4 KB
Raw

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

2019-04-03 吴亲库里 库里的深夜食堂

✏️描述

给你一个单链表,判断是不是回文链表,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,此时的结点就在链表的最中间,当前节点不需要去进行比较,只需要比较它的左右两侧是否相等即可.

联系

​