Palindrome Linked List
题目:
Implement a function to check if a linked list is a palindrome.
分析:
无
解法:
public class Solution {
/**
* @param head a ListNode
* @return a boolean
*/
public ListNode reverseList(ListNode head) {
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode prev = dummy;
while (head.next != null) {
ListNode newhead = head.next;
head.next = newhead.next;
newhead.next = prev.next;
prev.next = newhead;
}
return dummy.next;
}
public boolean isPalindrome(ListNode head) {
// Write your code here
if (head == null || head.next == null) {
return true;
}
if (head.next.next == null) {
return head.val == head.next.val;
}
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode head2 = slow.next;
slow.next = null;
head2 = reverseList(head2);
while (head != null && head2 != null) {
if (head.val != head2.val) {
return false;
} else {
head = head.next;
head2 = head2.next;
}
}
return true;
}
}