Info
新版网站会员 即将涨价;已支持老用户续费~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
234. Palindrome Linked List | 234. 回文链表 | 🟢 |
- | 剑指 Offer II 027. 回文链表 | 🟢 |
前文 数组双指针技巧汇总 和 子序列问题解题思路 讲解了回文串和回文序列相关的问题,先来简单回顾下。
寻找回文串的核心思想是从中心向两端扩展:
// 在 s 中寻找以 s[left] 和 s[right] 为中心的最长回文串
String palindrome(String s, int left, int right) {
// 防止索引越界
while (left >= 0 && right < s.length()
&& s.charAt(left) == s.charAt(right)) {
// 双指针,向两边展开
left--;
right++;
}
// 返回以 s[left] 和 s[right] 为中心的最长回文串
return s.substring(left + 1, right);
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// 在 s 中寻找以 s[left] 和 s[right] 为中心的最长回文串
string palindrome(string s, int left, int right) {
// 防止索引越界
while (left >= 0 && right < s.length()
&& s[left] == s[right]) {
// 双指针,向两边展开
left--;
right++;
}
// 返回以 s[left] 和 s[right] 为中心的最长回文串
return s.substr(left + 1, right - left - 1);
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
def palindrome(s: str, left: int, right: int) -> str:
# 在 s 中寻找以 s[left] 和 s[right] 为中心的最长回文串
# 防止索引越界
while left >= 0 and right < len(s) and s[left] == s[right]:
# 双指针,向两边展开
left -= 1
right += 1
# 返回以 s[left] 和 s[right] 为中心的最长回文串
return s[(left + 1):right]
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
//在s中寻找以s[left]和s[right]为中心的最长回文串
func palindrome(s string, left int, right int) string {
//防止索引越界
for left >= 0 && right < len(s) && s[left] == s[right] {
//双指针,向两边展开
left--
right++
}
//返回以s[left]和s[right]为中心的最长回文串
return s[left+1 : right]
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var palindrome = function(s, left, right) {
// 防止索引越界
while (left >= 0 && right < s.length && s.charAt(left) == s.charAt(right)) {
// 双指针,向两边展开
left--;
right++;
}
// 返回以 s[left] 和 s[right] 为中心的最长回文串
return s.substring(left + 1, right);
};
因为回文串长度可能为奇数也可能是偶数,长度为奇数时只存在一个中心点,而长度为偶数时存在两个中心点,所以上面这个函数需要传入 l
和 r
。
而判断一个字符串是不是回文串就简单很多,不需要考虑奇偶情况,只需要双指针技巧,从两端向中间逼近即可:
boolean isPalindrome(String s) {
// 一左一右两个指针相向而行
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
bool isPalindrome(string s) {
//一左一右两个指针相向而行
int left = 0, right = s.length() - 1;
while (left < right) {
if (s[left] != s[right]) { //判断左右指针对应字符是否相等
return false;
}
left++;
right--;
}
return true;
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
def isPalindrome(s: str) -> bool:
# 一左一右两个指针相向而行
left, right = 0, len(s) - 1
while left < right:
if s[left] != s[right]:
return False
left += 1
right -= 1
return True
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// 将给定的字符串 s 转换成小写字母,并剔除其字母以外的字符
func isPalindrome(s string) bool {
s = strings.ToLower(s) // 转换成小写字母
left, right := 0, len(s)-1 // 一左一右两个指针相向而行
for left < right {
if !unicode.IsLetter(rune(s[left])) { // 剔除左指针不是字母的字符
left++
continue
}
if !unicode.IsLetter(rune(s[right])) { // 剔除右指针不是字母的字符
right--
continue
}
if s[left] != s[right] { // 比较左右指针是否相等
return false
}
left++
right--
}
return true
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// 使用 var 关键字声明函数 isPalindrome,参数为字符串 s
var isPalindrome = function(s) {
// 左右两个指针相向而行
let left = 0, right = s.length - 1;
while (left < right) {
// 若左右指针的值不相同,则 s 不是回文字符串
if (s.charAt(left) !== s.charAt(right)) {
return false;
}
left++;
right--;
}
// 否则 s 是回文字符串
return true;
};
以上代码很好理解吧,因为回文串是对称的,所以正着读和倒着读应该是一样的,这一特点是解决回文串问题的关键。
下面扩展这一最简单的情况,来解决:如何判断一个「单链表」是不是回文。
一、判断回文单链表
看下力扣第 234 题「回文链表」:
输入一个单链表的头结点,判断这个链表中的数字是不是回文,函数签名如下:
boolean isPalindrome(ListNode head);
比如说:
输入: 1->2->null
输出: false
输入: 1->2->2->1->null
输出: true
这道题的关键在于,单链表无法倒着遍历,无法使用双指针技巧。
那么最简单的办法就是,把原始链表反转存入一条新的链表,然后比较这两条链表是否相同。关于如何反转链表,可以参见前文 递归翻转链表的一部分。
其实,借助二叉树后序遍历的思路,不需要显式反转原始链表也可以倒序遍历链表,下面来具体聊聊。
对于二叉树的几种遍历方式,我们再熟悉不过了:
void traverse(TreeNode root) {
// 前序遍历代码
traverse(root.left);
// 中序遍历代码
traverse(root.right);
// 后序遍历代码
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
void traverse(TreeNode* root) {
// 前序遍历代码
traverse(root->left);
// 中序遍历代码
traverse(root->right);
// 后序遍历代码
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
def traverse(root: TreeNode) -> None:
# 前序遍历代码
traverse(root.left)
# 中序遍历代码
traverse(root.right)
# 后序遍历代码
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
func traverse(root *TreeNode) {
// 前序遍历代码
traverse(root.left)
// 中序遍历代码
traverse(root.right)
// 后序遍历代码
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var traverse = function(root) {
// 前序遍历代码
traverse(root.left);
// 中序遍历代码
traverse(root.right);
// 后序遍历代码
};
在 学习数据结构的框架思维 中说过,链表兼具递归结构,树结构不过是链表的衍生。那么,链表其实也可以有前序遍历和后序遍历:
void traverse(ListNode head) {
// 前序遍历代码
traverse(head.next);
// 后序遍历代码
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
void traverse(ListNode* head) {
// 前序遍历代码
traverse(head->next);
// 后序遍历代码
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
def traverse(head: ListNode):
# 前序遍历代码
traverse(head.next)
# 后序遍历代码
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
func traverse(head *ListNode) {
// 前序遍历代码
traverse(head.Next)
// 后序遍历代码
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var traverse = function(head) {
// 前序遍历代码
traverse(head.next);
// 后序遍历代码
}
这个框架有什么指导意义呢?如果我想正序打印链表中的 val
值,可以在前序遍历位置写代码;反之,如果想倒序遍历链表,就可以在后序遍历位置操作:
/* 倒序打印单链表中的元素值 */
void traverse(ListNode head) {
if (head == null) return;
traverse(head.next);
// 后序遍历代码
print(head.val);
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
/* 倒序打印单链表中的元素值 */
void traverse(ListNode* head) {
if (head == NULL) return;
traverse(head->next);
// 后序遍历代码
print(head->val);
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
# 倒序打印单链表中的元素值
def traverse(head: ListNode):
if head is None:
return
traverse(head.next)
# 后序遍历代码
print(head.val)
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// 倒序打印单链表中的元素值
func traverse(head *ListNode) {
if head == nil {
return
}
traverse(head.Next)
// 后序遍历代码
print(head.Val)
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
/**
* 倒序打印单链表中的元素值
*/
function traverse(head) {
if (head === null) {
return;
}
traverse(head.next);
// 后序遍历代码
console.log(head.val);
}
说到这了,其实可以稍作修改,模仿双指针实现回文判断的功能:
class Solution {
// 从左向右移动的指针
ListNode left;
// 从右向左移动的指针
ListNode right;
// 记录链表是否为回文
boolean res = true;
boolean isPalindrome(ListNode head) {
left = head;
traverse(head);
return res;
}
void traverse(ListNode right) {
if (right == null) {
return;
}
// 利用递归,走到链表尾部
traverse(right.next);
// 后序遍历位置,此时的 right 指针指向链表右侧尾部
// 所以可以和 left 指针比较,判断是否是回文链表
if (left.val != right.val) {
res = false;
}
left = left.next;
}
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class Solution {
public:
// 从左向右移动的指针
ListNode* left;
// 从右向左移动的指针
ListNode* right;
// 记录链表是否为回文
bool res = true;
bool isPalindrome(ListNode* head) {
left = head;
traverse(head);
return res;
}
void traverse(ListNode* right) {
if (right == nullptr) {
return;
}
// 利用递归,走到链表尾部
traverse(right->next);
// 后序遍历位置,此时的 right 指针指向链表右侧尾部
// 所以可以和 left 指针比较,判断是否是回文链表
if (left->val != right->val) {
res = false;
}
left = left->next;
}
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# 从左向右移动的指针
left = None
# 从右向左移动的指针
right = None
# 记录链表是否为回文
res = True
def isPalindrome(self, head: ListNode) -> bool:
self.left = head
self.traverse(head)
return self.res
def traverse(self, right: ListNode):
if right is None:
return
# 利用递归,走到链表尾部
self.traverse(right.next)
# 后序遍历位置,此时的 right 指针指向链表右侧尾部
# 所以可以和 left 指针比较,判断是否是回文链表
if self.left.val != right.val:
self.res = False
self.left = self.left.next
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
func isPalindrome(head *ListNode) bool {
left := head
res := true
var traverse func(*ListNode)
traverse = func(right *ListNode) {
if right == nil {
return
}
// 利用递归,走到链表尾部
traverse(right.Next)
// 后序遍历位置,此时的right指针指向链表右侧尾部
// 所以可以和left指针比较,判断是否是回文链表
if left.Val != right.Val {
res = false
}
left = left.Next
}
traverse(head)
return res
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var Solution = function() {
// 从左向右移动的指针
this.left = null;
// 从右向左移动的指针
this.right = null;
// 记录链表是否为回文
this.res = true;
}
Solution.prototype.isPalindrome = function(head) {
this.left = head;
this.traverse(head);
return this.res;
}
Solution.prototype.traverse = function(right) {
if (right == null) {
return;
}
// 利用递归,走到链表尾部
this.traverse(right.next);
// 后序遍历位置,此时的 right 指针指向链表右侧尾部
// 所以可以和 left 指针比较,判断是否是回文链表
if (this.left.val != right.val) {
this.res = false;
}
this.left = this.left.next;
}
这么做的核心逻辑是什么呢?实际上就是把链表节点放入一个栈,然后再拿出来,这时候元素顺序就是反的,只不过我们利用的是递归函数的堆栈而已。如果不好理解,可以看下面这个可视化面板,你可以不断点击 traverse(right.next);
这一行代码,就能看出 left, right
的移动过程了:
当然,无论造一条反转链表还是利用后序遍历,算法的时间和空间复杂度都是 O(N)。下面我们想想,能不能不用额外的空间,解决这个问题呢?
二、优化空间复杂度
更好的思路是这样的:
1、先通过 双指针技巧 中的快慢指针来找到链表的中点:
ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 指针现在指向链表中点
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
ListNode* slow, *fast;
slow = fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
// slow 指针现在指向链表中点
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# slow 指针现在指向链表中点
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var slow, fast *ListNode
slow, fast = head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
//slow 现在指向链表的中点
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var slow, fast;
slow = fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 指针现在指向链表中点
![](/algo/images/%E5%9B%9E%E6%96%87%E9%93%BE%E8%A1%A8/1.jpg)
2、如果fast
指针没有指向null
,说明链表长度为奇数,slow
还要再前进一步:
if (fast != null)
slow = slow.next;
![](/algo/images/%E5%9B%9E%E6%96%87%E9%93%BE%E8%A1%A8/2.jpg)
3、从slow
开始反转后面的链表,现在就可以开始比较回文串了:
ListNode left = head;
ListNode right = reverse(slow);
while (right != null) {
if (left.val != right.val)
return false;
left = left.next;
right = right.next;
}
return true;
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
ListNode* left = head;
ListNode* right = reverse(slow);
while (right != nullptr) {
if (left->val != right->val)
return false;
left = left->next;
right = right->next;
}
return true;
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
left, right = head, reverse(slow)
while right:
if left.val != right.val:
return False
left, right = left.next, right.next
return True
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
left := head
right := reverse(slow)
for right != nil {
if left.Val != right.Val {
return false
}
left = left.Next
right = right.Next
}
return true
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var isPalindrome = function(head) {
let left = head;
let right = reverse(findMid(head));
while (right !== null) {
if (left.val !== right.val) {
return false;
}
left = left.next;
right = right.next;
}
return true;
};
![](/algo/images/%E5%9B%9E%E6%96%87%E9%93%BE%E8%A1%A8/3.jpg)
至此,把上面 3 段代码合在一起就高效地解决这个问题了,其中 reverse
函数很容易实现:
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast != null)
slow = slow.next;
ListNode left = head;
ListNode right = reverse(slow);
while (right != null) {
if (left.val != right.val)
return false;
left = left.next;
right = right.next;
}
return true;
}
ListNode reverse(ListNode head) {
ListNode pre = null, cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class Solution {
public:
bool isPalindrome(ListNode* head) {
ListNode* slow, *fast;
slow = fast = head;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
if (fast != nullptr)
slow = slow->next;
ListNode* left = head;
ListNode* right = reverse(slow);
while (right != nullptr) {
if (left->val != right->val)
return false;
left = left->next;
right = right->next;
}
return true;
}
ListNode* reverse(ListNode* head) {
ListNode* pre = nullptr, *cur = head;
while (cur != nullptr) {
ListNode* next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast:
slow = slow.next
left = head
right = self.reverse(slow)
while right:
if left.val != right.val:
return False
left = left.next
right = right.next
return True
def reverse(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
return pre
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
/*
Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
*/
// global function
func isPalindrome(head *ListNode) bool {
var slow, fast *ListNode
slow, fast = head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
if fast != nil {
slow = slow.Next
}
left, right := head, reverse(slow)
for right != nil {
if left.Val != right.Val {
return false
}
left = left.Next
right = right.Next
}
return true
}
// nested function
func reverse(head *ListNode) *ListNode {
var pre, cur *ListNode
pre, cur = nil, head
for cur != nil {
next := cur.Next
cur.Next = pre
pre = cur
cur = next
}
return pre
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {boolean}
*/
var isPalindrome = function(head) {
let slow, fast;
slow = fast = head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
if (fast !== null)
slow = slow.next;
let left = head;
let right = reverse(slow);
while (right !== null) {
if (left.val !== right.val)
return false;
left = left.next;
right = right.next;
}
return true;
};
function reverse(head) {
let pre = null, cur = head;
while (cur !== null) {
let next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
算法过程如下 GIF 所示:
![](/algo/images/kgroup/8.gif)
算法总体的时间复杂度 O(N),空间复杂度 O(1),已经是最优的了。
我知道肯定有读者会问:这种解法虽然高效,但破坏了输入链表的原始结构,能不能避免这个瑕疵呢?
其实这个问题很好解决,关键在于得到p, q
这两个指针位置:
![](/algo/images/%E5%9B%9E%E6%96%87%E9%93%BE%E8%A1%A8/4.jpg)
这样,只要在函数 return 之前加一段代码即可恢复原先链表顺序:
p.next = reverse(q);
篇幅所限,我就不写了,读者可以自己尝试一下。
三、最后总结
首先,寻找回文串是从中间向两端扩展,判断回文串是从两端向中间收缩。对于单链表,无法直接倒序遍历,可以造一条新的反转链表,可以利用链表的后序遍历,也可以用栈结构倒序处理单链表。
具体到回文链表的判断问题,由于回文的特殊性,可以不完全反转链表,而是仅仅反转部分链表,将空间复杂度降到 O(1)。
《labuladong 的算法笔记》已经出版,关注公众号查看详情;后台回复「全家桶」可下载配套 PDF 和刷题全家桶:
![](/algo/images/souyisou2.png)