【leetcode】回文链表

0、相似题目

回文子字符串的个数

最多删除一个字符得到回文

有效的回文

一、题目描述

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

输入: head = [1,2,3,3,2,1]
输出: true

二、代码思路

跟回文串一致

三、 代码题解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {
        //先处理边界条件
        if(head.next == null) return true;
        //两个节点的情况
        if(head.next.next == null) return head.val == head.next.val ? true : false;
        //使用双指针遍历判断 or 从中间开始分散两边来判断
        List<ListNode> list = new ArrayList();
        ListNode headTemp = head;
        while(headTemp != null) {
            list.add(headTemp);
            headTemp = headTemp.next;
        }
        int l = 0;
        int r = list.size() - 1;
        while(l < r) {
            if(list.get(l).val != list.get(r).val) return false;
            l++;
            r--;
        }
        return true;
        //当然也可以用其他手段来解决:
        //比方说：解决删除一个字符的回文串时，可以先遍历，直到找到有一对字符不相同，则以这两个
        //字符为中心，判断分别删除这两个字符之后，字符串是不是回文串。
        
    }
}