最近在看程序员面试金典，在链表部分看到有一题问如何判断链表是否是回文串，然后想到白书中也有对最长回文子串的讨论，故想做一点总结。
链表的数据结构是这样子滴：
public class Node { public int val; public Node next; public Node(int val) { this.val = val; next = null; } public void appendToTail(Node node) { Node curNode = this; while (curNode.next != null) { curNode = curNode.next; } curNode.next = node; } }这是面试金典中的一个题目，大体的思路有以下两种
1、将链表前半段入栈，然后从后半段开始依次与栈顶元素比较。
Java代码如下：
/** * 将链表前半部分放入栈中（注意奇数和偶数个） * 当遍历链表后半部分的时候，一次弹出栈中的 * 元素，检验对应位置的元素是否相同。 * @param head * @return */ private static boolean isPalindrome(Node head) { //如果链表为空或者只有一个节点，那么链表是回文串 if (head == null || head.next == null) { return true; } //设置快慢指针，控制入栈的节点个数为节点数的一半。 Node fastNode = head, slowNode = head; Stack<Node> stack = new Stack<>(); while (fastNode != null && fastNode.next != null) { stack.push(slowNode); fastNode = fastNode.next.next;//快指针走两步 slowNode = slowNode.next;//慢指针走一步 } //如果最后快指针是空，则链表节点数为偶数，且此时慢指针 //指向中间位置（偶数有两个中心位置）的右侧，故不需要后移。 //若不为空，则链表节点数为奇数，且慢指针指向中心位置， //若要比较需要向后移动一位。 if (fastNode != null) { slowNode = slowNode.next; } //遍历链表后半部分并以此与栈中元素比较 while (slowNode != null && !stack.isEmpty()) { if (slowNode.val != stack.peek().val) { return false; } slowNode = slowNode.next; stack.pop(); } return true; }
2、递归，递归链表的前半段，返回以中心位置为轴的对应位置元素的比较结果。
Java代码：
/** * 使用递归的思路，递归链表的前一半，返回的时候 * 依次与后半部分对应的节点比较，如果都对应相等 * 则为回文串，否则不是。 * @param head * @return */ public boolean isPalindrom(Node head) { //得到链表的长度，递归过程中需要使用 int len = getLindedLength(head); return isPalin(head, len).isPalindrom; } /** * 递归求解函数。每次向下递归时，传入的长度减2， * 到达链表中间结束递归并开始判断，返回判断结果。 * 到达中间，即递归结束条件有三种情况： * 长度为0：说明链表为空 * 长度为1：说明链表长度是奇数，此时指向中间节点 * 长度为2：说明链表长度为偶数，中间节点有两个 * 此时指向左边的中间节点。 * @param head * @param length * @return */ private returnStruct isPalin(Node head, int length) { if (length == 0) {//链表为空 returnStruct struct = new returnStruct(); struct.isPalindrom = true; struct.aimNode = null; return struct; } else if (length == 1) {//链表长度为奇数 returnStruct struct = new returnStruct(); //中间节点不用判断，返回它的下一个节点，用于 //递归返回后与它的上一个节点比较 struct.isPalindrom = true; struct.aimNode = head.next; return struct; } else if (length == 2){//长度为偶数 //需要比较一下两个中间节点是否相同，并返回 //靠右的中间节点的下一个节点，用于递归返回 //后与靠左的中间节点的上一个节点比较 returnStruct struct = new returnStruct(); struct.isPalindrom = head.val == head.next.val ? true : false; struct.aimNode = head.next.next; return struct; } //拿到返回的比较结果 returnStruct returnStruct = isPalin(head.next, length - 2); if (!returnStruct.isPalindrom) {//如果前面有不符合回文的节点直接返回false return returnStruct; } //比较当前节点和返回的节点（也就是与当前节点以中心点为轴的对称节点）是否相同 returnStruct.isPalindrom = head.val == returnStruct.aimNode.val ? true : false; returnStruct.aimNode = returnStruct.aimNode.next; return returnStruct; } /** * 得到指定链表的长度 * @param head * @return */ private int getLindedLength(Node head) { if (head == null) { return 0; } Node node = head; int len = 0; while (node != null) { len++; node = node.next; } return len; } /** * 用于包装递归返回值的类。 * 因为递归需要返回两个值，因此使用该类 * 来封装。 */ class returnStruct { //表示上一次比较是否是回文串 boolean isPalindrom; Node aimNode;//表示与当前节点对应比较的节点 }
这道题是白书中的一道题。题目大意是：输入一个字符串，求其最长回文子串。判断时，忽略所有标点符号和空格，忽略大小写。但是输出的时候保持原样。
样例输入：Confuciuss say : Madam,I’m Adam.
样例输出：Madam,I’m Adam
这道题的思路也很简单
1、处理字符串，过滤标点与空格，并记录字母在原串中的位置。
2、判断过滤后的字符串是否是回文。遍历字符串，以当前位置为中心向外扩散，每次扩散长度加一并检查该子串是否是回文串。注意子串长度的奇偶性。
Java代码：
/** * 得到最长回文字串函数。 * 遍历每个元素，从当前元素开始，依次查看以自身为中心（分奇偶）的 * 长度递增的子串是否是回文字符串，并更新当前最长子串的长度和位置 * @param string * @return */ public String getLPS(String string) { if (string == null) { return null; } if (string.length() == 0) { return ""; } char[] strs = string.toCharArray(); //过滤无用自字符，用来存放需要查找的字符 char[] m = new char[strs.length]; //用来记录对应位置的字符在原数组中的位置 int[] p = new int[strs.length]; int mLen = 0; for (int i = 0; i < strs.length; i++) { if (Character.isAlphabetic(strs[i])) { p[mLen] = i; m[mLen++] = Character.toLowerCase(strs[i]); } } int maxLen = Integer.MIN_VALUE; int x = 0, y = 0; //遍历数组，以当前字符为中心检查不同长度的子串是否为回文串 for (int i = 0; i < mLen; i++) { //奇数长度的子串 for (int j = 0; i - j >= 0 && i + j < mLen; j++) { if (m[i - j] != m[i + j]) { break; } if (2 * j + 1 > maxLen) { maxLen = 2 * j + 1; x = p[i - j];//记录最长子串位置 y = p[i + j]; } } //偶数长度的子串 for (int j = 0; i - j >= 0 && i + j + 1 < mLen; j++) { if (m[i - j] != m[i + j + 1]) { break; } if (2 * j + 2 > maxLen) { maxLen = 2 * j + 2; x = p[i - j]; y = p[i + j + 1]; } } } StringBuilder build = new StringBuilder(); for (int i = x; i <= y; i++) { build.append(strs[i]); } return build.toString(); }