目录
1、题目介绍
2、解题思路
2.1、暴力破解法
2.2、快慢指针反转链表
文章来源地址https://www.toymoban.com/news/detail-713940.html
1、题目介绍
原题链接： 234. 回文链表 - 力扣（LeetCode）
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
- 链表中节点数目在范围[1, 10^5] 内
- 0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
2、解题思路
判断回文，就是判断是否是对称的。有些朋友对于数组的回文判断非常熟悉，但是对链表的回文判断可能就无从下手了，其实都一样的。有一种非常简单的方式就是将链表转化成数组，然后就是判断该数组是否回文就可以了，这种方式统称暴力破解法，简单粗暴。下面就来先带着大家看一下这道题的暴力破解法。
2.1、暴力破解法
一共为两个步骤：
- 复制链表值到数组列表中。
- 使用双指针法判断是否为回文。
首先按照题目要求的最大大小定义一个大小为100001的整型数组，接着通过循环遍历将链表中每个结点的值取出放入数组中，最后通过两个指针，一个从左一个从右分别判断是否相等，只要遇到一个不相等就返回false，否则当循环结束时返回true。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool isPalindrome(struct ListNode* head){
int arr[100001] = {0},num = 0;
while(head)
{
arr[num] = head->val;
head = head->next;
num++;
}
int i= 0;
int j =0;
for(i = 0,j = num-1; i<j; i++,j--)
{
if(arr[i]!=arr[j])
{
return false;
}
}
return true;
}时间复杂度：O(n)，其中 n 指的是链表的元素个数。
- 第一步：遍历链表并将值复制到数组中，O(n)。
- 第二步：双指针判断是否为回文，执行了 O(n/2) 次的判断，即O(n)。
- 总的时间复杂度：O(2n)=O(n)。
空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。
进阶：你能否用
O(n)时间复杂度和O(1)空间复杂度解决此题？下面带大家做一下本题的进阶，使用快慢指针反转链表实现空间复杂度为O(1)的算法。
2.2、快慢指针反转链表
整个流程可以分为以下五个步骤：
- 找到前半部分链表的尾节点。
- 反转后半部分链表。
- 判断是否回文。
- 恢复链表。
- 返回结果。
对于第一步找到前半部分链表的尾结点，我们可以计算链表结点个数然后再找到前半部分的尾结点，也可以通过快慢指针一次遍历找到前半部分的尾结点。
慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。
此时slow就是前半部分的尾结点，而slow的下一个结点就是后半部分的头结点。于是让fast回到slow的next结点处，将后半部分的结点全部反转，然后slow即前半部分的尾结点置空。
紧接着将让slow从head重新出发，fast从最后结点出发，分别向中间结点靠近并判断，只要相等就一直向中间靠近，遇到不相同时直接返回false，否则当循环退出时返回true。
最后在将反转链表还原回去即可。
代码实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool isPalindrome(struct ListNode* head){
if(head == NULL || head->next == NULL)
{
return true;
}
struct ListNode* n1 = head;
struct ListNode* n2 = head;
//快慢指针遍历
while(n2->next != NULL && n2->next->next != NULL)
{
n1 = n1->next; //慢指针
n2 = n2->next->next; //快指针
}
n2 = n1->next; //右边第一个
n1->next = NULL;
struct ListNode* n3;
//反转右半边链表
while(n2 != NULL)
{
n3 = n2->next; //n3存放n2的next
n2->next = n1;
n1 = n2;
n2 = n3;
}
//当循环结束时n1所指向的位置就是链表最后一个结点，
n2 = n3 = n1; //将n2和n3指回最后一个节点
n1 = head; //n1回到头结点
bool flag = true;
//判断是否是回文
while(n1 != NULL && n2 != NULL)
{
if(n1->val != n2->val)
{
flag = false;
break;
}
n1 = n1->next;
n2 = n2->next;
}
//还原链表
n2 = n3->next; //n3此时指向最后一个结点，因为反转了链表，n3的next就是上一个结点
n3->next = NULL;
while(n2!=NULL)
{
n1 = n2->next;
n2->next = n3;
n3 = n2;
n2 = n1;
}
return flag;
}时间复杂度：O(n)，其中 n 指的是链表的大小。
空间复杂度：O(1)。我们只会修改原本链表中节点的指向，而在堆栈上的堆栈帧不超过 O(1)。
更多【LeetCode刷题】 推荐：
【LeetCode力扣】86. 分隔链表-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133942678?spm=1001.2014.3001.5501【LeetCode力扣】297. 二叉树的序列化与反序列化-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133827375【LeetCode力扣】LCR170 使用归并排序的思想解决逆序对问题（详细图解）_Hacynn的博客-CSDN博客https://blog.csdn.net/zzzzzhxxx/article/details/133578735
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！文章来源：https://www.toymoban.com/news/detail-713940.html
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！
到了这里，关于【LeetCode力扣】234 快慢指针 | 反转链表 | 还原链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
