leetcode234. 回文链表

题目

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

示例 1：

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

示例 2：

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

提示：

• 链表中节点数目在范围[1, 105] 内
• 0 <= Node.val <= 9

 方法一

思路：

将链表转为数组，然后双指针判断即可。

代码

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        vector<int> vt; // 栈存放数组
        while(head){    // 链表 -> 栈
            vt.push_back(head->val);
            head = head->next;
        }
        // 定义双指针来对数组进行回文判断
        int left = 0, right = vt.size()-1;
        while(left < right){
            if(vt[left++] != vt[right--]){
                return false;
            }
        }
        return true;
    }
};

learn

这里因数组大小不好定义，所以可以使用 栈vector

方法二

反转链表，同时遍历，若不同，则返回false。

不知道为何这个方法总是返回false

 ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* cur = head;
        ListNode* next;
        while(cur){
            next = cur->next;   // cur的后面结点
            cur->next = prev;   // cur的前面结点
            prev = cur;
            cur = next;            
        }
        return prev;
    }
class Solution {    
public:
    bool isPalindrome(ListNode* head) {
        ListNode* reverse = reverseList(head);
        while(reverse && head){
            if(reverse->val != head->val){
                return false;
            }
            reverse = reverse->next;
            head = head->next;
        }
        return true;
    }
};