如何判断回文链表
https://labuladong.gitee.io/algo/2/17/19/
看完这篇文章，你不仅可以学习算法例程，还可以去LeetCode获取以下问题：
24.回文链表(简单)
———
我们之前写过两篇关于回文和回文序列的文章。
寻找回文的核心思想是从中心向两端扩展：
字符串回文(字符串s，int l，int r){ 0
//防止索引超出界限
while (l=0 r s.size()
s[l]==s[r]) {
//向两边扩展
l-；r；
}
//返回以s[l]和s[r]为中心的最长回文字符串
返回s.substr(l 1，r-l-1)；
}
因为回文长度可能是奇数或偶数，长度为奇数时只有一个中心点，长度为偶数时有两个中心点，所以上述函数需要传入L和r。
判断一个字符串是否是回文字符串要简单得多。不需要考虑平价。它只需要“双指针技术”从两端向中间逼近：
bool isPalindrome(字符串){ s
int left=0，right=s . length-1；
而(左右){ 0
if (s[left]！=s[右])
返回false
向左；右-；
}
返回真；
}
上面的代码很容易理解，因为回文是对称的，所以前面读和后面读应该是一样的，这是解决回文问题的关键。
让我们展开这个最简单的案例来解决：如何判断一个“单链表”是否是回文。
一、判断回文单链表
输入单个链表的头节点，判断该链表中的数字是否为回文：
/**
*单链表节点的定义：
*公共类列表节点
* int val
*下一个列表节点；
* }
*/
布尔isPalindrome(列表节点头)；
输入： 1-2-null。
输出：为假
输入： 1-2-2-1-null。
输出：为真
这个问题的关键是单链表不能向后遍历，不能使用双指针技术。
那么最简单的方法就是将原来的链表反转成新的链表，然后比较两个链表是否相同。如何反转链表，请参考前面递归反转链表的部分。
实际上，有了二叉树后序遍历的思想，就可以反向遍历链表，而不需要显式地反向原来的链表。下面我们来详细说说。
我们熟悉二叉树的几种遍历方法：
void traverse(TreeNode根){ 0
//序言遍历代码
导线(左根)；
//中间顺序遍历代码
遍历(根.右)；
//后序列遍历代码
}
在学习数据结构的框架思维中，都说链表具有递归结构，树结构只是链表的一个派生物。然后，链表实际上可以有前序遍历和后序遍历：
void遍历(列表节点头){ 0
//序言遍历代码
遍历(head . next)；
//后序列遍历代码
}
这个框架的指导意义是什么？如果我想以正序打印链表中的val值，可以在正向序列遍历位置写代码；相反，如果你想反向遍历链表，你可以在后序遍历位置进行操作：
/*以相反的顺序打印单个链表中的元素值*/
void遍历(列表节点头){ 0
if (head==null)返回；
遍历(head . next)；
//后序列遍历代码
print(head . val)；
}
话虽如此，其实可以稍加修改模仿双指针来实现回文判断的功能：
//左指针
左侧列表节点；
布尔isPalindrome(列表节点头){ 0
左=头；
返回导线(头部)；
}
布尔遍历(列表节点右){ 0
if (right==null)返回tru
e;
boolean res = traverse(right.next);
// 后序遍历代码
res = res (right.val == left.val);
left = left.next;
return res;
}
这么做的核心逻辑是什么呢实际上就是把链表节点放入一个栈，然后再拿出来，这时候元素顺序就是反的，只不过我们利用的是递归函数的堆栈而已。
当然，无论造一条反转链表还是利用后序遍历，算法的时间和空间复杂度都是 O(N)。下面我们想想，能不能不用额外的空间，解决这个问题呢
二、优化空间复杂度
更好的思路是这样的：
1、先通过双指针技巧中的快慢指针来找到链表的中点：
ListNode slow, fast;
slow = fast = head;
while (fast != null fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow 指针现在指向链表中点
2、如果fast指针没有指向null，说明链表长度为奇数，slow还要再前进一步：
if (fast != null)
slow = slow.next;
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;
至此，把上面 3 段代码合在一起就高效地解决这个问题了，其中reverse函数很容易实现：
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;
}
算法总体的时间复杂度 O(N)，空间复杂度 O(1)，已经是最优的了。
我知道肯定有读者会问：这种解法虽然高效，但破坏了输入链表的原始结构，能不能避免这个瑕疵呢
其实这个问题很好解决，关键在于得到p, q这两个指针位置：
这样，只要在函数 return 之前加一段代码即可恢复原先链表顺序：
p.next = reverse(q);
篇幅所限，我就不写了，读者可以自己尝试一下。
三、最后总结
首先，寻找回文串是从中间向两端扩展，判断回文串是从两端向中间收缩。对于单链表，无法直接倒序遍历，可以造一条新的反转链表，可以利用链表的后序遍历，也可以用栈结构倒序处理单链表。
具体到回文链表的判断问题，由于回文的特殊性，可以不完全反转链表，而是仅仅反转部分链表，将空间复杂度降到 O(1)。
＿＿＿＿＿＿＿＿＿＿＿＿＿
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/84596.html