[数据结构与算法]leetcode234 回文链表

解题思路：

只要把链表从中间断开，再把其中一个链表反转，就可以依次比较节点值是否相同。
1.寻找链表中间节点，可采用快慢指针，快指针是慢指针速度的两倍，那么，当快指针走到尾部时，慢指针走到链表中间。
2. 反转其中一个链表，之间做过。

class Solution {
public:

    ListNode* reverse_list(ListNode* head)
    {
        ListNode* pre = nullptr;
        ListNode* cur = head;
        ListNode* temp;
        while(cur!=nullptr)
        {
            temp=cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

    bool isPalindrome(ListNode* head) {
        if(head==nullptr||head->next==nullptr)
            return true;

        ListNode * fast = head;
        ListNode * slow = head;
        ListNode * pre; //记录链表断开的节点，也即是中点的前一个节点
        while(fast!=nullptr&&fast->next!=nullptr)
        {
            pre =  slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr; //断开链表

        ListNode * cur1 = head; //新链表1
        ListNode * cur2 = reverse_list(slow); //新链表2
        
        while(cur1!=nullptr)
        {
            if(cur1->val!=cur2->val)
                return false;
            cur1 = cur1->next;
            cur2 = cur2->next; 
        }
        return true;
    }
        
};