234. 回文链表
思路
- 获取链表长度
- 将链表一分为二
- 反转其中一个链表进行比较
复杂度
时间复杂度:O(n)
空间复杂度:O(1)
代码
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val) { $this->val = $val; }
* }
*/
class Solution {
/**
* @param ListNode $head
* @return Boolean
*/
function isPalindrome($head) {
$p = $head;
// 长度
$len = 0;
while($p != null) {
$len++;
$p = $p->next;
}
// 第二段链表的起始位置
$start = (int)(($len + 1)/2) + 1;
$p = $head;
$counter = 1;
while($counter < $start) {
$counter++;
if($counter == $start){
// 拆链
$tmp = $p->next;
$p->next = null;
$p = $tmp;
} else {
$p = $p->next;
}
}
// 反转第二段链表
$p = $this->reverseList($p);
while($p->val !== null) {
if($p->val !== $head->val){
return false;
}
$head = $head->next;
$p = $p->next;
}
return true;
}
/**
* 反转链表
* @param ListNode $head
* @return ListNode
*/
function reverseList($head) {
$p = null;
while($head != null) {
$tmp = $head;
$head = $head->next;
$tmp->next = $p;
$p = $tmp;
}
return $p;
}
}