链表题目总结 -- 回文链表

一. 从中心开始找最大的回文字符串

• 题目链接：没有。给定一个字符串s，从s的中心开始，寻找最大的回文字符串。
• 函数名：public static String palindrome(String s, int left, int right) ；

1. 思路简述

• 因为链表的节点如果是奇数，那么中心就是一个点；链表的节点数是偶数，中心就是两个点。所以要传入left和right两个参数变量。
• 这里说一下substring，当中的索引和数组的下标不太一样，可以理解为这里的索引仅仅标志着存储空间的开始，索引之后才是真正的存储空间，看下图：
  
• 最后一次循环后，left = -1，right = 3，按照substring的原理，left+1就可以，right不用动。
  

2. 代码

	public static String palindrome(String s, int left, int right){while(left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {left--;right++;}return s.substring(left + 1, right);}//主函数public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.nextLine();int left, right;if(s.length() % 2 == 0) {right = s.length() / 2;left = right - 1;}else{left = right = s.length() / 2;}System.out.println("left" + left + "   right:" + right);System.out.println(palindrome(s,left,right));}

3. 总结

• 主要还是substring这一块的原理搞清楚，索引只是标志着存储空间的开始，而不是真的已经存储了。

二. 判断是否为回文字符串

• 题目链接：没有。给定一个字符串s，判断这个字符串是否为回文字符串。
• 函数名：public static Boolean isPalindrome(String s) ；

1. 思路简述

• 从两头开始，向里面比较。

2. 代码

public static boolean isPalindrome(String s){int left = 0;int right = s.length() - 1;while(left < right){if(s.charAt(left) == s.charAt(right)){left++;right--;}elsereturn false;}return true;
}

3.总结

• 很简单，注意边界

三. 判断是否是回文链表

• 题目链接：https://leetcode.cn/problems/palindrome-linked-list/

1. 思路简述

• 运用递归的栈进行比较，树是链表的变形，是链表衍生出来的。

2. 代码

class Solution {public ListNode left = null; public boolean traverse(ListNode right){if(right == null)return true;boolean res = traverse(right.next) && (left.val == right.val);left = left.next;return res;}public boolean isPalindrome(ListNode head) {left = head;return traverse(left);}
}

3. 总结

• 时间复杂度：o(n)
• 空间复杂度：o(n)，也可以直接调用api中的stack类来实现栈存储节点，然后判断。
• 还有一种方法，是把链表装进数组，然后再用索引依次判断是否为回文链表，这里也需要申请n个单位的空间复杂度，所以空间复杂度也是o(n)，博主这里就不实现了。

---

• 太牛了，东哥这个思想：树是由链表衍生出来的，所以链表也可以前序、后序遍历。

• 树的遍历：

void traverse(TreeNode root) {// 前序遍历代码traverse(root.left);// 中序遍历代码traverse(root.right);// 后序遍历代码
}

• 链表的遍历：

void traverse(ListNode head) {// 前序遍历代码traverse(head.next);// 后序遍历代码
}

• 这种遍历能干什么呢，其实可以实现链表的正序或者逆序输出，看下面：

//正序输出
public static void traverse(ListNode head) {if(head == null)return;// 前序遍历代码	System.out.println(head.val);traverse(head.next);// 后序遍历代码
}//逆序输出
public static void traverse(ListNode head) {if(head == null)return;// 前序遍历代码traverse(head.next);// 后序遍历代码System.out.println(head.val);
}

4. 优化解法

• 这里所提到的优化，主要还是在空间复杂度上进行优化。
• 使用双指针，返回链表中心节点，将后一半链表反转，再依次比较两个链表的值。

public static ListNode reverseList_iteration(ListNode head){ListNode pre, cur, nxt;pre = null; cur = head; nxt = head;while(cur != null){//标记后继指针nxt = cur.next;//反转cur.next = pre;//更新 cur、pre指针pre = cur;cur = nxt;}return pre;
}
public static Boolean ispalindrome(ListNode head){if(head == null)return true;ListNode fast, slow;fast = slow = 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 = reverseList_iteration(slow.next);while(right != null){if(right.val == left.val){left = left.next;right = right.next;}else return false;}slow.next = reverseList_iteration(right);return true;
}

为什么有这一行呢？（ if(fast! != null) slow = slow.next;），看下图：很显然，当链表数目为奇数的时候，slow指针并没有指到对应的位置，只有向后再走一步，链表反转才有意义。

这个程序执行完之后，虽然运行成功，但是链表结构发生了改变，如下图：

如果想要保证链表结构不变 ，救灾输出的时候把链表还原出来，也就是这里东哥所说的q为头节点的链表反转之后，用p指针将它们连起来，如下图：

如果引入p，q指针显然又要申请额外的内存空间，不划算，我们在原来程序的基础上做一个改进，看下面的代码：

public boolean isPalindrome(ListNode head) {ListNode fast, slow;fast = slow = head;//这样就保证不管是奇数还是偶数的链表，slow指针都差一个才到位置，也就是p指针指的地方while(fast.next != null && fast.next.next != null){slow = slow.next;fast = fast.next.next;}ListNode left = head;//而right指针正好就是q指针指的地方，这样就完美的解决了不额外申请空间的问题ListNode right = reverseList_iteration(slow.next);while(right != null){if(right.val == left.val){left = left.next;right = right.next;}else return false;}slow.next = reverseList_iteration(right);return true;

• 时间复杂度：o(n)
• 空间复杂度：o(1)

参考：
https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-8f30d/ru-he-pan–f9d3c/
https://leetcode.cn/problems/palindrome-linked-list/solution/hui-wen-lian-biao-by-leetcode-solution/