新题来咯，道新的面回文链表
回文链表
力扣题目链接：https://leetcode-cn.com/problems/palindrome-linked-list/
请判断一个链表是试题否为回文链表。
示例 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; // 慢指针，找到链表中间分位置，云南idc服务商作为分割 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
// 方法一，使用数组 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; } } Python
#数组模拟 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 pre