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;}
};