class Solution {
/**
* 逆转链表
* @param head
* @return
*/
private static ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
ListNode next = head.next;
while (next != null) {
cur.next = pre;
pre = cur;
cur = next;
next = next.next;
}
cur.next = pre;
return cur;
}
/**
* 发现中节点
* @param head
* @return
*/
private static ListNode findMid(ListNode head) {
if (head == null) {
return null;
}
ListNode cur = head;
ListNode next = head;
while (next.next != null && next.next.next != null) {
cur = cur.next;
next = next.next.next;
}
return cur;
}
public static boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode mid = findMid(head);
ListNode tail = reverse(mid);
ListNode p1 = head;
ListNode p2 = tail;
while (p1 != null && p2 != null) {
if (p1.val != p2.val) {
return false;
}
p1 = p1.next;
p2 = p2.next;
}
reverse(tail);
return true;
}
private static void print(ListNode head) {
while (head != null) {
System.out.println(head.val);
head = head.next;
}
}
public static void main(String[] args) {
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
ListNode n3 = new ListNode(3);
ListNode n4 = new ListNode(2);
ListNode n5 = new ListNode(1);
n1.next = n2;
// n2.next = n3;
// n3.next = n4;
// n4.next = n5;
// ListNode head = findMidPre(n1);
System.out.println(isPalindrome(n1));
// print(head);
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
©著作权归作者所有：来自51CTO博客作者天一涯51CTO的原创作品，如需转载，请注明出处，否则将追究法律责任