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

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        // write code here
        //判断链表是否是回文结构要用到快慢指针
        //即当快指针走完整个链表时慢指针要么正好在链表的后半部分（长度为偶）
        //要么慢指针正好走到后半部分的前一个节点（长度为奇数）
        ListNode*fastP=head,*lowP=head;//定义快慢指针
        while(fastP&&fastP->next)//循环结束条件为快指针不为空或者快指针的后面还有节点
        {
            fastP=fastP->next->next;//快指针一次走两步
            lowP=lowP->next;//慢指针一次走一步
        }
        ListNode* end=lowP;
        ListNode* Head=reverse(lowP);//反转后半部分链表
        while(Head&&head!=end)
        {
            if(Head->val!=head->val)
                return false;
             Head=Head->next;
            head=head->next;
        }
        return true;
    }
    ListNode* reverse(ListNode* head)
    {
        ListNode* tmp=NULL,*rear=head->next;
        while(rear)
        {
            head->next=tmp;
            tmp=head;
            head=rear;
            rear=head->next;
        }
        head->next=tmp;
        return head;
    }
};