题解 | #判断一个链表是否为回文结构#

<?php

/*class ListNode{
    var $val;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 the head
 * @return bool布尔型
 */
function isPail( $head )
{
    if($head == null || $head->next == null){
        return true;
    }
    // 快慢指针法找到中点
    $slow = $head;
    $fast = $head->next;
    while($fast != null && $fast->next != null){
        $slow = $slow->next;
        $fast = $fast->next->next;
    }
    // 反转后半段链表
    $pre = null;
    $beg = $slow->next;
    $slow->next = null;
    while($beg != null){
        $temp = $beg->next;
        $beg->next = $pre;
        $pre = $beg;
        $beg = $temp;
    }
    // 比较
    $start = $head;
    $end = $pre;
    while($start != null && $end != null ){
        if($start->val != $end->val){
            return false;
        }
        $start = $start->next;
        $end = $end->next;
    }
    return true;
}

逆转一半链表法：通过快慢指针找到中点，分成两个list，逆转后面一半链表，两个链表一一比较