leetCode ✏Leetcode之PHP版题目解析（234. Palindrome Linked List）
✏描述
给你一个单链表,判断是不是回文链表,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,此时的结点就在链表的最中间,当前节点不需要去进行比较,只需要比较它的左右两侧是否相等即可.
转载链接：https://leetcode.cn/
![[爱了]](/js/img/d1.gif)
![[尴尬]](/js/img/d16.gif)