首先，回文相关题目在leetcode可不止这几道，随便搜索就很多：
肯定也不止这些，
回文串（正着读和反着读都一样的字符串，比如aba和abba就是回文串，abac就不是回文串）问题。注意回文串的长度可能是奇数也可能是偶数，解决思路就是双指针。
就拿这篇开个头吧。
开唠~
这篇的回文子串就分为三个方面
在字符串中找一个最长的回文子串在字符串中找找有多少个回文子串 判断一个单链表是不是回文链表
1.在字符串中找一个最长的回文子串
一种思路就是：既然回文串正着读和反着读都一样，那么我们如果把S反转，成为s’,然后在s和s’中寻找最长公共子串，这样就能找到最长的回文子串。（但是比如，字符串aacxycaa反转后aacyxcaa，最长字符串aac,但是正确的最长回文子串应该是aa而不是aac,所以这种思路不对，但是以后咱们要多想想这种类似的思路转化），所以说这种有例外，不能用。另外一种思路就是，寻找回文串的核心思想是：从中间开始向两边扩散来判断回文串。判断回文串是从两端向中间收缩。
class Solution {
//时间复杂度为O(N^2)，最坏情况下两个指针要把整个字符串走两遍哦,空间复杂度为O(1)
public String longestPalindrome(String s) {
//官话判空
if(s == null || s.length() == 0){
return "";
}
int left = 0;
int right = 0;
for(int i = 0; i < s.length(); i++){
//为什么要扩散两遍，就是因为字符串的长度有奇数也有偶数，所以只从s[i]向两边扩散的话s[i]没有，那怎么办呀对不对
//以s[i]和s[i]为中心向外扩散得到的最长回文子串
int length1 = expandFromCenter(s, i, i);
//以s[i]和s[i + 1]为中心向外扩散得到的最长回文子串
int length2 = expandFromCenter(s, i, i + 1);
//在result、length1、length2三个中挑出最长的回文子串
int result = (length1 > length2) ? length1 : length2;
if(result > (right - left)){
left = i - (result - 1) / 2;
right = i + result / 2;
}
}
return s.substring(left, right + 1);
}
//函数传入两个指针left和right,
public int expandFromCenter(String s, int left, int right){
//如果当两个指针指向的两边的字母相同,也就是s.charAt(left) == s.charAt(right)，我们就可以继续扩展。如果两边的字母不同，我们就可以停止扩展，因为在这之后的子串都不能是回文串了
while((left >= 0) && (right < s.length()) && (s.charAt(left) == s.charAt(right))){
//指针由中间向两边展开
left--;
right++;
}
//返回以s[left]和s[right]为中心的最长的回文子串
return right - left - 1;
}
}
2.在字符串中找找有多少个回文子串
class Solution {
public int countSubstrings(String s) {
//时间复杂度为O(N^2)，最坏情况下两个指针要把整个字符串走两遍哦,空间复杂度为O(1)
//官话判空
if(s == null || s.length() == 0){
return 0;
}
int result = 0;
for(int i = 0; i < 2 * s.length() - 1; i++){
int left = i / 2;
int right = i / 2 + i % 2;
//如果两边的字母相同,也就是s.charAt(left) == s.charAt(right)，我们就可以继续扩展。如果两边的字母不同，我们就可以停止扩展，因为在这之后的子串都不能是回文串了
while((left >= 0) && (right < s.length()) && (s.charAt(left) == s.charAt(right))){
//指针由中间向两边展开
left--;
right++;
result++;
}
}
return result;
}
}
3.判断一个单链表是不是回文链表
判断一个字符串是不是回文串
//判断一个字符串是不是回文串就不需要考虑奇偶情况，只需要双指针技巧，从两端向中间逼近
boolean isPalindrome(String s){
int left = 0;
int right = s.length - 1;
while(left < right){
if(s[left] != s[right]){
return false;
}
left++;
right--;
}
return true;
}
判断一个单链表是不是回文链表
思路就是把原始链表反转存于一条新的链表中，然后比较这两条链表是否相同。
class Solution {
ListNode left;
public boolean isPalindrome(ListNode head) {
//左侧指针
left = head;
return traverse(left);
}
public boolean traverse(ListNode right){
if(right == null){
return true;
}
//迭代，一步两步
boolean result = traverse(right.next);
result = result && (right.val == left.val);
//或者这样写能更明白一点:
//boolean result = (traverse(right.next)) && (right.val == left.val);
left = left.next;
return result;
}
}
其中部分代码是借鉴反转整个链表：
class Solution {
public ListNode reverseList(ListNode head) {
//递归函数的base case，也相当于链表的官话判空
if(head == null){
return null;
}
if(head.next == null){
return head;//相当于链表只有一个节点时再怎么反转也是他自己，就直接返回自己即可
}
ListNode last = reverseList(head.next);
head.next.next = head;//反转链表节点之间的指针
head.next = null;//当链表递归反转之后，新的头节点变成了last，head变成了新链表的最后一个节点，别忘了链表的末尾指针要指向null，所以才有z了这一句代码
return last;
}
}
当然啦，反转链表也有很多提醒咯，以后再唠咯
