LeetCode234. 回文链表(day0025_1)

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

 输入：head = [1,2,2,1]
 输出：true

示例 2：

 输入：head = [1,2]
 输出：false

提示：

• 链表中节点数目在范围[1, 105] 内

• 0 <= Node.val <= 9

把链表装成数组，判断是否回文:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> nums;
        while(head){
            nums.push_back(head->val);
            head=head->next;
        }
        for(int i=0,j=nums.size()-1;i<j;i++,j--){
            if(nums[i]!=nums[j])return false;
        }
        return true;
    }
};

反转后半部分链表：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==nullptr&&head->next==nullptr)return true;
        ListNode* pre=head;
        ListNode* fast=head;
        ListNode* slow=head;
        while(fast&&fast->next){
            pre=slow;
            slow=slow->next;
            fast=fast->next->next;
        } 
        pre->next=nullptr;
        ListNode* cur1=head;
        ListNode* cur2=reverseList(slow);
        while(cur1){
            if(cur1->val!=cur2->val)return false;
            cur1=cur1->next;
            cur2=cur2->next;
        }
        return true;
    }
    //反转链表
    ListNode* reverseList(ListNode* head){
        ListNode* temp;
        ListNode* cur=head;
        ListNode* pre=nullptr;
        while(cur){
            temp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
    }
};