一道新的面试题回文链表你会么？

新题来咯，道新的面回文链表

回文链表

力扣题目链接：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; // 慢指针，找到链表中间分位置，云服务器提供商作为分割         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 

很赞哦!（57）