🍋1.回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
题目链接：【蓝桥Java每日一练】————5.按键持续时间最长的键https://leetcode-cn.com/problems/palindrome-linked-list/
🍋朴素做法
朴素的做法当然是转换成判断普通回文的题目，由于链表的长度在一开始是未知的，所以我们需要用集合去遍历存储链表的所有元素，然后写一个双指针判断回文的方法判断该链表是否是回文链表。
时间复杂度O(N)：N为链表的长度，一次循环遍历链表，一次循环判断回文，所以总体时间复杂度为O(N)
空间复杂度O(N)：N为链表的长度，主要是存储链表元素集合的开销。
class Solution { public boolean isPalindrome(ListNode head) { //用来保存链表的值 List<Integer> list=new ArrayList<>(); int cur=0; ListNode node=head; while(node!=null){ list.add(node.val); node=node.next; } return test(list); } //判断是否是回文的方法，参数注意为List public boolean test(List<Integer> list){ int left=0; int right=list.size()-1; while(left<right){ if(list.get(left++)!=list.get(right--)){ return false; } } return true; } }
🍋进阶做法
在题目中的进阶要求是需要我们在时间复杂度O(n)且空间复杂度O(1)下完成，这就使得我们不可以通过遍历链表保存元素的方式去完成，必须得在原链表上进行判断。在这我们把链表的后半部分反转，然后去判断前半部分和后半部分是否相等，然后对于被我们反转过的链表是否需要反转回来都是可行的，但毕竟使用者不希望自己的链表被修改，所以建议还是修改回来。
时间复杂度O（n）:其中 n 指的是链表的大小
空间复杂度O（1)
整个流程可以分为以下五个步骤：
找到前半部分链表的尾节点。
反转后半部分链表。
判断是否回文。
恢复链表（有或无都可以）。
返回结果。
class Solution { public boolean isPalindrome(ListNode head) { if(head == null || head.next == null) return true; // 找中点 1=>1 123=>2 1234=>2 ListNode A_end = mid(head); ListNode B_start = A_end.next; A_end.next = null; // 翻转后半部分 B_start = reverse(B_start); // 比对 boolean res = compare(head, B_start); // 还原 A_end.next = reverse(B_start); return res; } // 链表找中点，快慢指针法 ListNode mid(ListNode head) { ListNode p = head; ListNode q = head; while(q.next != null && q.next.next != null) { p = p.next; q = q.next.next; } return p; } // 链表反转模板 ListNode reverse(ListNode head) { ListNode pre = null; ListNode cur = head; while(cur != null) { ListNode temp = cur.next; cur.next = pre; pre = cur; // 归位 cur = temp; } return pre; } // 链表比对模板(len(B) <= len(A)) boolean compare(ListNode A, ListNode B) { while(B != null) { if(A.val != B.val) return false; A = A.next; B = B.next; } return true; } }
