【每日一题】链表系列(3) —— 回文链表

写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我热爱AI、热爱分享、热爱开源！ 这博客是我对学习的一点总结与记录。如果您也对 深度学习、机器视觉、算法、Python、C++ 感兴趣，可以关注我的动态，我们一起学习，一起进步~
我的博客地址为：【AI 菌】的博客
我的Github项目地址是：【AI 菌】的Github

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/palindrome-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一、题目描述

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

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

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

进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
 

二、解题思路：双指针法

在解这道题之前，我们先来回顾一下数组和链表这两种列表的区别：

• 数组列表底层是使用数组存储值，我们可以通过索引在 O(1) 的时间访问列表任何位置的值，这是由基于内存寻址的方式。
• 链表存储的是称为节点的对象，每个节点保存一个值和指向下一个节点的指针。访问某个特定索引的节点需要 O(n)的时间，因为要通过指针获取到下一个位置的节点。

因此，判断数组列表是否回文很简单，我们可以使用双指针法来比较两端的元素，并向中间移动：一个指针从起点向中间移动，另一个指针从终点向中间移动，这需要 O(n) 的时间。

但是，对于链表列表来说，并没有这么简单，因为不论是正向访问还是反向访问都不是 O(1)。

而将链表的值复制到数组列表中是 O(n)。因此，最简单的方法就是先将链表的值复制到数组列表中，再使用双指针法判断。

C++实现过程如下：

class Solution {
public: bool isPalindrome(ListNode* head) { //将链表的值复制到数组列表 vector<int>temp; while(head != nullptr){ temp.push_back(head->val); head = head->next; } //使用双指针法判断是否为回文 int i=0, j = temp.size()-1; while(i<j){ if(temp[i] != temp[j]) return false; ++i; --j; } return true; }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
 

复杂度分析：

• 时间复杂度：O(n)，其中 n 指的是链表的元素个数。第一步：将链表的值复制到数组列表时间复杂度为O(n)；第二步：使用双指针法判断是否为回文也为O(n)。总的时间复杂度：O(n)+O(n)=O(n)
• 空间复杂度：O(n)O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表temp来存放链表的元素值。

由于水平有限，博客中难免会有一些错误，有纰漏之处恳请各位大佬不吝赐教！

推荐文章

• 【C++21天养成计划】不聊学习只谈干货（Day1）
• 【人生苦短，我学 Python】序言——不学点Python你就out了？
• TF2.0深度学习实战（一）：分类问题之手写数字识别

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/114953273