参与本项目，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！
请判断一个链表是否为回文链表。
示例 1:
- 输入: 1->2
- 输出: false
示例 2:
- 输入: 1->2->2->1
- 输出: true
最直接的想法，就是把链表装成数组，然后再判断是否回文。
代码也比较简单。如下：
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector<int> vec;
ListNode* cur = head;
while (cur) {
vec.push_back(cur->val);
cur = cur->next;
}
// 比较数组回文
for (int i = 0, j = vec.size() - 1; i < j; i++, j--) {
if (vec[i] != vec[j]) return false;
}
return true;
}
};上面代码可以在优化，就是先求出链表长度，然后给定vector的初始长度，这样避免vector每次添加节点重新开辟空间
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* cur = head;
int length = 0;
while (cur) {
length++;
cur = cur->next;
}
vector<int> vec(length, 0); // 给定vector的初始长度，这样避免vector每次添加节点重新开辟空间
cur = head;
int index = 0;
while (cur) {
vec[index++] = cur->val;
cur = cur->next;
}
// 比较数组回文
for (int i = 0, j = vec.size() - 1; i < j; i++, j--) {
if (vec[i] != vec[j]) return false;
}
return true;
}
};
分为如下几步：
- 用快慢指针，快指针有两步，慢指针走一步，快指针遇到终止位置时，慢指针就在链表中间位置
- 同时用pre记录慢指针指向节点的前一个节点，用来分割链表
- 将链表分为前后均等两部分，如果链表长度是奇数，那么后半部分多一个节点
- 将后半部分反转 ，得cur2，前半部分为cur1
- 按照cur1的长度，一次比较cur1和cur2的节点数值
如图所示：
代码如下：
class Solution {
public:
bool isPalindrome(ListNode* head) {
if (head == nullptr || head->next == nullptr) return true;
ListNode* slow = head; // 慢指针，找到链表中间分位置，作为分割
ListNode* fast = head;
ListNode* pre = head; // 记录慢指针的前一个节点，用来分割链表
while (fast && fast->next) {
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = nullptr; // 分割链表
ListNode* cur1 = head; // 前半部分
ListNode* cur2 = reverseList(slow); // 反转后半部分，总链表长度如果是奇数，cur2比cur1多一个节点
// 开始两个链表的比较
while (cur1) {
if (cur1->val != cur2->val) return false;
cur1 = cur1->next;
cur2 = cur2->next;
}
return true;
}
// 反转链表
ListNode* reverseList(ListNode* head) {
ListNode* temp; // 保存cur的下一个节点
ListNode* cur = head;
ListNode* pre = nullptr;
while(cur) {
temp = cur->next; // 保存一下 cur的下一个节点，因为接下来要改变cur->next
cur->next = pre; // 翻转操作
// 更新pre 和 cur指针
pre = cur;
cur = temp;
}
return pre;
}
};// 方法一，使用数组
class Solution {
public boolean isPalindrome(ListNode head) {
int len = 0;
// 统计链表长度
ListNode cur = head;
while (cur != null) {
len++;
cur = cur.next;
}
cur = head;
int[] res = new int[len];
// 将元素加到数组之中
for (int i = 0; i < res.length; i++){
res[i] = cur.val;
cur = cur.next;
}
// 比较回文
for (int i = 0, j = len - 1; i < j; i++, j--){
if (res[i] != res[j]){
return false;
}
}
return true;
}
}
// 方法二，快慢指针
class Solution {
public boolean isPalindrome(ListNode head) {
// 如果为空或者仅有一个节点，返回true
if (head == null && head.next == null) return true;
ListNode slow = head;
ListNode fast = head;
ListNode pre = head;
while (fast != null && fast.next != null){
pre = slow; // 记录slow的前一个结点
slow = slow.next;
fast = fast.next.next;
}
pre.next = null; // 分割两个链表
// 前半部分
ListNode cur1 = head;
// 后半部分。这里使用了反转链表
ListNode cur2 = reverseList(slow);
while (cur1 != null){
if (cur1.val != cur2.val) return false;
// 注意要移动两个结点
cur1 = cur1.next;
cur2 = cur2.next;
}
return true;
}
ListNode reverseList(ListNode head){
// 反转链表
ListNode tmp = null;
ListNode pre = null;
while (head != null){
tmp = head.next;
head.next = pre;
pre = head;
head = tmp;
}
return pre;
}
}#数组模拟
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
length = 0
tmp = head
while tmp: #求链表长度
length += 1
tmp = tmp.next
result = [0] * length
tmp = head
index = 0
while tmp: #链表元素加入数组
result[index] = tmp.val
index += 1
tmp = tmp.next
i, j = 0, length - 1
while i < j: # 判断回文
if result[i] != result[j]:
return False
i += 1
j -= 1
return True
#反转后半部分链表
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if head == None or head.next == None:
return True
slow, fast = head, head
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None # 分割链表
cur1 = head # 前半部分
cur2 = self.reverseList(slow) # 反转后半部分，总链表长度如果是奇数，cur2比cur1多一个节点
while cur1:
if cur1.val != cur2.val:
return False
cur1 = cur1.next
cur2 = cur2.next
return True
def reverseList(self, head: ListNode) -> ListNode:
cur = head
pre = None
while(cur!=None):
temp = cur.next # 保存一下cur的下一个节点
cur.next = pre # 反转
pre = cur
cur = temp
return prevar isPalindrome = function(head) {
const reverseList = head => {// 反转链表
let temp = null;
let pre = null;
while(head != null){
temp = head.next;
head.next = pre;
pre = head;
head = temp;
}
return pre;
}
// 如果为空或者仅有一个节点，返回true
if(!head && !head.next) return true;
let slow = head;
let fast = head;
let pre = head;
while(fast != null && fast.next != null){
pre = slow; // 记录slow的前一个结点
slow = slow.next;
fast = fast.next.next;
}
pre.next = null; // 分割两个链表
// 前半部分
let cur1 = head;
// 后半部分。这里使用了反转链表
let cur2 = reverseList(slow);
while(cur1 != null){
if(cur1.val != cur2.val) return false;
// 注意要移动两个结点
cur1 = cur1.next;
cur2 = cur2.next;
}
return true;
};数组模拟
function isPalindrome(head: ListNode | null): boolean {
const helperArr: number[] = [];
let curNode: ListNode | null = head;
while (curNode !== null) {
helperArr.push(curNode.val);
curNode = curNode.next;
}
let left: number = 0,
right: number = helperArr.length - 1;
while (left < right) {
if (helperArr[left++] !== helperArr[right--]) return false;
}
return true;
};反转后半部分链表
function isPalindrome(head: ListNode | null): boolean {
if (head === null || head.next === null) return true;
let fastNode: ListNode | null = head,
slowNode: ListNode = head,
preNode: ListNode = head;
while (fastNode !== null && fastNode.next !== null) {
preNode = slowNode;
slowNode = slowNode.next!;
fastNode = fastNode.next.next;
}
preNode.next = null;
let cur1: ListNode | null = head;
let cur2: ListNode | null = reverseList(slowNode);
while (cur1 !== null) {
if (cur1.val !== cur2!.val) return false;
cur1 = cur1.next;
cur2 = cur2!.next;
}
return true;
};
function reverseList(head: ListNode | null): ListNode | null {
let curNode: ListNode | null = head,
preNode: ListNode | null = null;
while (curNode !== null) {
let tempNode: ListNode | null = curNode.next;
curNode.next = preNode;
preNode = curNode;
curNode = tempNode;
}
return preNode;
}