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

亦凉 2022-10-23 00:52 170阅读 0赞

> 写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我`热爱AI、热爱分享、热爱开源`！ 这博客是我对学习的一点总结与记录。如果您也对 `深度学习、机器视觉、算法、Python、C++` 感兴趣，可以关注我的动态，我们一起学习，一起进步~  
> 我的博客地址为：[【AI 菌】的博客][AI]  
> 我的Github项目地址是：[【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) 空间复杂度解决此题？

## 二、解题思路：双指针法 ##

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

*  数组列表底层是使用数组存储值，我们可以通过索引在 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;
        }
    };

复杂度分析：

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

--------------------

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

![在这里插入图片描述][2020090613542669.png_pic_center]  
***推荐文章***

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

[AI]: https://blog.csdn.net/wjinjie
[AI _Github]: https://github.com/Keyird/DeepLearning-TensorFlow2.0
[2020090613542669.png_pic_center]: /images/20221022/efb55c088533419c825aaa77cb9778c2.png
[C_21_Day1]: https://blog.csdn.net/wjinjie/article/details/105316043
[Python_Python_out]: https://ai-wx.blog.csdn.net/article/details/110674503
[TF2.0]: https://ai-wx.blog.csdn.net/article/details/104700834