题目描述
示例 1：
输入： 1->2
输出： false
示例 2：
输入： 1->2->2->1
输出： true
进阶：
- 你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解题思路与代码
- 这是一道有关链表操作的题，不算特别的难。考到了链表的几个基础的操作，像是反转链表，创建一个新的链表，找到链表的中间节点，用什么方式去找。
- 所以，需要你对链表的基础操作有一定的理解，如果你对链表的操作了熟于心的话，这道题真的是简单的不在话下，但是如果对链表只是基本了解的话，这道题还是有一丢丢难度的。
方案一：构造一条新链表（原链表的反转）之后对比
这里有一点十分需要注意的是：这里的反转链表，不是在原链表上进行反转操作，而是创建一个新链表，新链表的内容是反转后的原链表，之后我们才可以继续对比操作。- 很多新手，或者说对链表不熟悉的人来说，很容易就
ListNode * prev = head;开始准备反转链表了，殊不知它们已经修改了原链表的内容了，拿着修改后的原链表与自己做对比，那不就100%会出错嘛~
具体的代码如下：
class Solution {
public:
bool isPalindrome(ListNode* head) {
// 创建前驱节点，并且为重新创建一条新的链表（节点反转后的链表）做准备
ListNode * tail = head;
ListNode * newHead = nullptr;
// 创建一条链表（节点反转后的链表）
while(tail){
ListNode * temp = new ListNode(tail->val);
temp->next = newHead;
tail = tail->next;
newHead = temp;
}
// 检查两条链表是否相等，若相等则返回true，否则false
while(newHead) {
if(newHead->val != head->val) return false;
head = head->next;
newHead = newHead->next;
}
return true;
}
};
复杂度分析
时间复杂度：
该代码包含两个循环。第一个循环遍历整个链表以创建一个反向链表。第二个循环遍历链表以比较原始链表和反向链表的节点。因此，总的时间复杂度为O(n) + O(n) = O(2n)，在大O表示法中，我们忽略常数，所以时间复杂度为O(n)。
空间复杂度：
在创建反向链表的过程中，为每个节点分配了新的内存，所以空间复杂度为O(n)，其中n为链表的长度。
方案二：优化，快慢指针！
- 这个方案，我们使用快慢指针的方式，先找到这个链表的中间节点，紧接着，反转后半部分的链表，之后就进行对比就可以了。
- 由于是在原链表上面进行操作，空间复杂度可以降低到O(1)
- 快慢指针找到中间节点的好处是，不用去管奇数还是偶数节点。如果你还不理解的话，请你在纸上画一画草图，离开就能出来了。
具体的代码如下：
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(head == nullptr || head->next == nullptr) return true;
ListNode * slow = head;
ListNode * fast = head;
// 找到中间节点
while(fast->next != nullptr && fast->next->next != nullptr){
slow = slow->next;
fast = fast->next->next;
}
// 反转后半链表
ListNode * prev = nullptr;
while(slow != nullptr){
ListNode * temp = slow->next;
slow->next = prev;
prev = slow;
slow = temp;
}
// 开始逐一对比
while(head != nullptr && prev !=nullptr){
if(head->val != prev->val) return false;
head = head->next;
prev = prev->next;
}
return true;
}
};
复杂度分析
时间复杂度：
- 这段代码包含三个主要步骤：找到链表的中点，反转链表的后半部分，然后比较两个半链表。这三个步骤都需要遍历链表，所以总的时间复杂度是 O(n) + O(n) + O(n) = O(3n)。但在大O表示法中，我们会忽略常数，所以最终的时间复杂度是O(n)。
空间复杂度：
- 这段代码并没有使用额外的空间来存储链表的节点。所有的操作都是在原来链表的基础上完成的，所以空间复杂度是O(1)。
总结
对于这道题的实际意义，可以从以下几个方面理解：
-
对数据结构的理解和操作：链表是一种基础且常用的数据结构，理解和掌握链表的操作是非常重要的。这道题测试了你对链表的理解和操作能力。
-
算法设计：这道题目需要你设计一个算法来解决问题。这考察了你的问题解决能力，包括如何将问题分解，如何设计算法，以及如何实现算法。
-
空间复杂度优化：题目进阶部分要求使用 O(1) 的空间复杂度来解决问题，这就需要你考虑如何在不增加额外空间的情况下解决问题。这是对你优化代码和理解空间复杂度的一个测试。
-
时间复杂度的理解：题目要求算法的时间复杂度为 O(n)，这就需要你保证你的算法在最坏的情况下也能在线性时间内完成。
-
实际应用：在实际的软件开发中，我们可能会遇到需要判断一个序列是否为回文的情况，例如检测字符串是否为回文。此题就可以作为实现该功能的一种思路。
所以，这道题目的主要意义在于锻炼和测试你的数据结构操作能力，算法设计能力，以及你对时间和空间复杂度的理解。同时，也可以帮助你在实际问题中更好地应用这些技巧和知识。
最后的最后，如果你觉得我的这篇文章写的不错的话，请给我一个赞与收藏，关注我，我会继续给大家带来更多更优质的干货内容。