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力扣】LCR170 使用归并排序的思想解决逆序对问题（详细图解）
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！
如果觉得作者写的不错，求给博主一个大大的点赞支持一下，你们的支持是我更新的最大动力！
