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?
先分成大小相同(可能长度差1) 两部分, reverse一个list. 再比较.
采用Runner Technique，结束时runner在最后一个element，walker在第一半的list的最后一个element，设置walker.next为 list2的head
这样做，第一半list会比第二半多，或者相等。
技巧来了：因为允许两个list不同的地方在于---第一半List可以多最后那一个element。方便起见，把第二个list reverse，挨个比过去，第一半的最后一个元素可以不比。如果reverse第一个list，要分别讨论:第一组对比不同是因为这个element是多余的那个, 还是因为本身不是palindrome，或者要计算两段的长度，总之很麻烦。
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution { 10 public boolean isPalindrome(ListNode head) { 11 if (head==null || head.next==null) return true; 12 ListNode dummy = new ListNode(-1); 13 dummy.next = head; 14 ListNode l1 = dummy; 15 ListNode l2 = dummy; 16 while (l1!=null && l1.next!=null) { 17 l1 = l1.next.next; 18 l2 = l2.next; 19 } 20 ListNode head1 = head; 21 ListNode head2 = l2.next; 22 l2.next = null; 23 24 head2 = reverse(head2); //head1‘s linkedlist may be longer, so if there length are not the same, it could only be in the end 25 26 while (head1 != null && head2 != null) { 27 if (head1.val != head2.val) return false; 28 head1 = head1.next; 29 head2 = head2.next; 30 } 31 return true; 32 } 33 34 public ListNode reverse(ListNode head) { 35 if (head == null) return null; 36 ListNode dummy = new ListNode(-1); 37 dummy.next = head; 38 ListNode end = head; 39 while (end.next != null) { 40 end = end.next; 41 } 42 while (dummy.next != end) { 43 ListNode cur = dummy.next; 44 ListNode next = cur.next; 45 cur.next = end.next; 46 end.next = cur; 47 dummy.next = next; 48 } 49 return dummy.next; 50 } 51 }
Leetcode: Palindrome Linked List
原文：http://www.cnblogs.com/EdwardLiu/p/5060228.html