【蓝桥Java每日一练】——9.回文链表

⭐️引言⭐️

           大家好啊，我是执梗。今天带来一道能检验链表基础的题，题目比较简单，但是想通过确实容易，但想使用更好复杂度的方法却不容易。非常推荐大家一起来尝试一下，将回文与链表相结合的基础题。

⭐️精彩回放⭐️
2022.1.16——Java每日一练【蓝桥Java每日一练】——8.计算力扣银行的钱2022.1.14——Java每日一练【蓝桥Java每日一练】——7.至少是其他数字两倍的最大数2022.1.11——Java每日一练【蓝桥Java每日一练】————6.二叉树的前中后序遍历（递归与迭代）2022.1.9——Java每日一练【蓝桥Java每日一练】————5.按键持续时间最长的键2022.1.8——Java每日一练【蓝桥Java每日一练】————4.移除元素

🍋1.回文链表

给你一个单链表的头节点

head

，请你判断该链表是否为回文链表。如果是，返回

true

；否则，返回

false

。

题目链接：【蓝桥Java每日一练】————5.按键持续时间最长的键

🍋朴素做法

        朴素的做法当然是转换成判断普通回文的题目，由于链表的长度在一开始是未知的，所以我们需要用集合去遍历存储链表的所有元素，然后写一个双指针判断回文的方法判断该链表是否是回文链表。

        时间复杂度O(N)：N为链表的长度，一次循环遍历链表，一次循环判断回文，所以总体时间复杂度为O(N)

        空间复杂度O(N)：N为链表的长度，主要是存储链表元素集合的开销。

classSolution {
    publicbooleanisPalindrome(ListNode head) {
        //用来保存链表的值
        List<Integer> list=newArrayList<>();
        int cur=0;
        ListNode node=head;
        while(node!=null){
            list.add(node.val);
            node=node.next;
        }
        return test(list);
    }
    //判断是否是回文的方法，参数注意为Listpublicbooleantest(List<Integer> list){
        int left=0;
        int right=list.size()-1;
        while(left<right){
            if(list.get(left++)!=list.get(right--)){
                returnfalse;
            }
        }
        returntrue;
    }
}

🍋进阶做法

       在题目中的进阶要求是需要我们在时间复杂度O(n)且空间复杂度O(1)下完成，这就使得我们不可以通过遍历链表保存元素的方式去完成，必须得在原链表上进行判断。在这我们把链表的后半部分反转，然后去判断前半部分和后半部分是否相等，然后对于被我们反转过的链表是否需要反转回来都是可行的，但毕竟使用者不希望自己的链表被修改，所以建议还是修改回来。

     时间复杂度O（n）:其中 n 指的是链表的大小

     空间复杂度O（1)

整个流程可以分为以下五个步骤：

1. 找到前半部分链表的尾节点。
2. 反转后半部分链表。
3. 判断是否回文。
4. 恢复链表（有或无都可以）。
5. 返回结果。

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;
    }
}

        **我是执梗，期待和你一起进步的过程！**