这个题标个简单,其实感觉也不简单,因为做题时候的思路感觉挺难(?)想的……我一时竟反应不出来。
按照数组的回文判断,直接双指针从数组的两边往中间判断即可。
但这是链表,要怎么操作才能把后面的值与前面的值同时判断?

有多种方法,简单的比如利用额外的存储空间,把它放进ArrayList中,即有索引可以比较。
下面介绍这种方法,没有使用额外的空间。
思想:把后半段链表逆序,与前半段逐一比较

具体实现:

  1. 找到链表的中间
  2. 反转后段链表
  3. 把反转后的链表与从头开始的链表进行比较
class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode cur = head,pre = head;
        // 找到下半段链表的头结点,用pre指向它
			// 这里使用的是快慢指针,也可以一轮遍历找出长度,然后再走总长度的一半
        while(cur != null && cur.next != null){
            cur = cur.next.next;
            pre = pre.next;
        }
        // 反转后半段链表
        ListNode newHead = null;
        while(pre != null){
            ListNode nextNode = pre.next;
            pre.next = newHead;
            newHead = pre;
            pre = nextNode;
        }
        // 逐一比较所有值,查看是否回文
        while(newHead != null){
            if(head.val != newHead.val){
                return false;
            }
            newHead = newHead.next;
            head = head.next;
        }
        
        return true;
    }
}

结合代码分析,可以代入两种情况:
A:[1, 2, 3, 2, 1]
B:[1, 2, 3, 3, 2, 1]

对于A,上面的代码,pre找到第二个2,然后从2开始反转链表
即最后会出现
head->1->2->3(注意,3是指向2的哦,不过不影响最终结点,可以无视之)
        ↘
newHead-> 1-> 2->null

对于B,同样的分析,
head-> 1-> 2-> 3
         ↘
newHead->1 ->2 -> 3->null