Given a singly linked list, determine if it is a palindrome.
Follow up: Could you do it in O(n) time and O(1) space?
我的思路很简单，先遍历一遍找到长度，然后用堆保存着前面一半的数据然后与后面的对比，不一样就false。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) return true; ListNode p1 = head; Stack<Integer> stack = new Stack<Integer>(); int len = 0, i = 0; while (p1 != null) { len++; p1 = p1.next; } p1 = head; while (i++ < len / 2) { stack.push(p1.val); p1 = p1.next; } if (len % 2 != 0) p1 = p1.next; while (p1 != null) { if (p1.val != stack.pop()) return false; p1 = p1.next; } return true; } }再提供一种方法，就是用反转来做。
public boolean isPalindrome(ListNode head) { if (head == null) { return true; } ListNode middle = findMiddle(head); middle.next = reverse(middle.next); ListNode p1 = head, p2 = middle.next; while (p1 != null && p2 != null && p1.val == p2.val) { p1 = p1.next; p2 = p2.next; } return p2 == null; } private ListNode findMiddle(ListNode head) { if (head == null) { return null; } ListNode slow = head, fast = head.next; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } return slow; } private ListNode reverse(ListNode head) { ListNode prev = null; while (head != null) { ListNode temp = head.next; head.next = prev; prev = head; head = temp; } return prev; }