LeetCode234--回文链表-蒲公英云

LeetCode234--回文链表

请判断一个链表是否为回文链表。
进阶：
你能否用 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) {
        $cur = $head;
        $arr = [];
        while (isset($cur)){
            $arr[] = $cur->val;
            $cur = $cur->next;
        }
        $len = count($arr);
        for($i=0; $i<floor($len/2); $i++){
            if($arr[$i] !== $arr[$len-$i-1]){
                return false;
            }
        }
        return true;
    }
}

解法二：

快慢指针找中点
使用快慢指针，可以找到链表的中点，就是两个指针开始的时候，都指向第一个元素，之后，往前走，快的指针一次走两步，慢的指针一次走一步，这样的话当快的走到头的时候，慢的正好走到中点位置。第一步先找到中点，同时将前面的部分反转，然后前面的一半和后面的一半再比较。这样的话，空间复杂度就是O(1)了。

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {
    /**
     * @param ListNode $head
     * @return Boolean
     */
    function isPalindrome($head) {
        $fast = $head;
        $slow = $head;
        $prev = null;
        $tmp = null;
        // 快慢指针遍历找中点的同时，把前部分进行反转
        while($fast && $fast->next){
            $prev = $slow;
            $fast = $fast->next->next;
            $slow = $slow->next;
            $prev->next = $tmp;
            $tmp = $prev;
        }
        //如果$fast不为空，则节点数为奇数，此时$slow正好是中间位置，需要往后移动一下
        if($fast){
            $slow = $slow->next;
        }
        //开始比较，前半部分是$prev指向，后半部分是$slow指向
        while($prev && $slow){
            if($prev->val != $slow->val){
                return false;
            }
            $prev = $prev->next;
            $slow = $slow->next;
        }
        return true;
    }
}