234. [E] Palindrome Linked List

https://leetcode.com/problems/palindrome-linked-list/

之前去 Facebook 面试遇到过这个题目,基于 206 的反转单链表 可以很容易解决。基本思路就是,从链表中间截断链表,反转后面半截,然后开始比较。

class Solution {
private int linkLength(ListNode head) {
int len = 0;
while(head != null) {
head = head.next;
len++;
}
return len;
}
// (..) <- (p) (c) -> (n) -> (..)
private ListNode reverseLink(ListNode head) {
ListNode p = null, c = head, n = null;
while (c != null) {
n = c.next;
c.next = p;
p = c;
c = n;
}
return p;
}
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
int len = linkLength(head);
ListNode t = head;
for (int i = 0; i < len / 2 - 1; i++) {
t = t.next;
}
ListNode tt = t.next;
t.next = null;
t = reverseLink(tt);
while (head != null) {
if (head.val != t.val) {
return false;
}
head = head.next;
t = t.next;
}
return true;
}
}