题解 | #链表的回文结构#

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
public:

struct ListNode* middleNode(struct ListNode* head) {
    //定义两个指针，快指针和慢指针
    //快指针一次走两步，慢指针一次走一步，fast->next为NULL或者fast为NULL时slow就为中间节点
    struct ListNode* fast,*slow;
    fast = slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

struct ListNode* reverseList(struct ListNode* head) {
    //如果链表为空直接返回head
    if(head == NULL)
    {
        return head;
    }
    //定义三个指针用来翻转链表
    struct ListNode* n1, *n2, *n3;
    n1 = NULL;
    n2 = head;
    n3 = head->next;
    //遍历链表并完成翻转操作
    while(n2)
    {
        n2->next = n1;
        n1 = n2;
        n2 = n3;
        if(n3 != NULL)
        {
            n3 = n3->next;
        }
    }
    return n1;
}

    bool chkPalindrome(ListNode* A) {
        // write code here
    ListNode* mid = middleNode(A);
    ListNode* ret = reverseList(mid);
    while(ret && A)
    {
        if(ret->val != A->val)
        return false;
        ret = ret->next;
        A = A->next;
    }
    return true;

    }
};