题意：判断一个链表是不是回文（中心对称）的
【反转链表】题解1：
得到原链表的反转链表，然后对比原链表与反转链表的内容是否一致即可。
反转链表版本代码
/**
* 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) {
ListNode rHead = reverse(head);
while(head != null) {
if(head.val != rHead.val) {
return false;
}
head = head.next;
rHead = rHead.next;
}
return true;
}
public ListNode reverse(ListNode head) {
return reverse(head, null);
}
public ListNode reverse(ListNode head, ListNode rLastHead) {
if(head == null) return null;
ListNode rHead = new ListNode(head.val, rLastHead);
if(head.next == null) return rHead;
return reverse(head.next, rHead);
}
}
【快慢指针+反转链表】题解2：
- 将链表一分为二，保证第一段子链表节点个数不小于第二段
通过快慢指针得到第二段子链表表头（先得到第一段子链表表尾，然后next得到第二段子链表表头）
快指针：每次移动两步
慢指针：每次移动一步 - 对第二段子链表进行反转
- 遍历第二段子链表，看其是否与第一段子链表val相同
快慢指针+反转链表版本代码
/**
* 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) {
ListNode fast = head;
ListNode low = head;
while(fast.next != null && fast.next.next != null) {
low = low.next;
fast = fast.next.next;
}
low = low.next;
ListNode rHead = reverse(low);
while(rHead != null) {
if(head.val != rHead.val) return false;
head = head.next;
rHead = rHead.next;
}
return true;
}
public ListNode reverse(ListNode head) {
return reverse(head, null);
}
public ListNode reverse(ListNode head, ListNode rLastHead) {
if(head == null) return null;
ListNode rHead = new ListNode(head.val, rLastHead);
if(head.next == null) return rHead;
return reverse(head.next, rHead);
}
}