
<p align="center">
  <a href="https://mp.weixin.qq.com/s/RsdcQ9umo09R6cfnwXZlrQ"><img src="https://img.shields.io/badge/PDF下载-代码随想录-blueviolet" alt=""></a>
  <a href="https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw"><img src="https://img.shields.io/badge/刷题-微信群-green" alt=""></a>
  <a href="https://space.bilibili.com/525438321"><img src="https://img.shields.io/badge/B站-代码随想录-orange" alt=""></a>
  <a href="https://mp.weixin.qq.com/s/QVF6upVMSbgvZy8lHZS3CQ"><img src="https://img.shields.io/badge/知识星球-代码随想录-blue" alt=""></a>
</p>
<p align="center"><strong>欢迎大家<a href="https://mp.weixin.qq.com/s/tqCxrMEU-ajQumL1i8im9A">参与本项目</a>，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们收益！</strong></p>

# 234.回文链表

题目链接：https://leetcode-cn.com/problems/palindrome-linked-list/

请判断一个链表是否为回文链表。

示例 1:
* 输入: 1->2
* 输出: false

示例 2:
* 输入: 1->2->2->1
* 输出: true


# 思路

## 数组模拟

最直接的想法，就是把链表装成数组，然后再判断是否回文。

代码也比较简单。如下：

```C++
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每次添加节点重新开辟空间

```C++
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的节点数值

如图所示：

<img src='https://code-thinking.cdn.bcebos.com/pics/234.回文链表.png' width=600> </img></div>

代码如下：

```C++
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;
    }
};
```


# 其他语言版本

## Java

```java
```

## Python

```python
```

## Go

```go
```

## JavaScript

```js
```


-----------------------
* 作者微信：[程序员Carl](https://mp.weixin.qq.com/s/b66DFkOp8OOxdZC_xLZxfw)
* B站视频：[代码随想录](https://space.bilibili.com/525438321)
* 知识星球：[代码随想录](https://mp.weixin.qq.com/s/QVF6upVMSbgvZy8lHZS3CQ)
<div align="center"><img src=../pics/公众号.png width=450 alt=> </img></div>

