Leetcode Palindrome Linked List

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?

根据回文串的特点，我们需要比较对应位置的值是否相等，那么我们首先需要找到链表的中点，这个可以用快慢指针来实现。使用快慢指针找中点的原理是fast和slow两个指针，每次快指针走两步，慢指针走一步，等快指针走完时，慢指针的位置就是中点。

方法一解题思路：

用栈，每次慢指针走一步，都把值存入栈中，等到达中点时，链表的前半段都存入栈中了，由于栈的后进先出的性质，就可以和后半段链表按照回文对应的顺序比较了。

但没法做到 O(1) space ，因此方法二才完全满足要求，事实上，方法二所需的运行时间的确小很多。

方法二解题思路：

1). 使用快慢指针寻找链表中点

2). 将链表的后半部分就地逆置，然后比对前后两半的元素是否一致

3). 恢复原始链表的结构（可选）

java code

 1 import java.util.Stack;
 2 
 3 public class PalindromeLinkedList {
 4     public class ListNode {
 5         int val;
 6         ListNode next;
 7         ListNode(int x) { val = x; }
 8     }
 9 
10     /*
11     method1: use stack to save the first half linked list
12     use fast and slow pointer, when fast pointer reaches the end, slow pointer       reaches the middle of LinkedList
13     * */
14     public boolean isPalindrome(ListNode head) {
15         if(head == null || head.next == null) { return true;}
16         ListNode slow = head, fast = head;
17         Stack<Integer> s = new Stack<Integer>();
18         s.push(head.val);
19         //find middle node
20         while(fast.next != null && fast.next.next != null) {
21             slow = slow.next;
22             fast = fast.next.next;
23             s.push(slow.val);
24         }
25         if(fast.next == null) {s.pop();}
26         while(slow.next != null) {
27             slow = slow.next;
28             int tmp = s.peek();
29             s.pop();
30             if(tmp != slow.val) { return false; }
31         }
32         return true;
33 
34     }
35 
36     /*
37     * method2
38     */
39     public boolean isPalindrome(ListNode head) {
40         if(head == null || head.next == null) { return true;}
41         ListNode slow = head, fast = head;
42         //find middle node
43         while(fast.next != null && fast.next.next != null) {
44             slow = slow.next;
45             fast = fast.next.next;
46         }
47         //reverse the second half linked list
48         ListNode last = slow.next, pre = head;
49         while(last.next != null ) {
50             ListNode tmp = last.next;
51             last.next = tmp.next;
52             tmp.next = slow.next;
53             slow.next = tmp;
54         }
55         while(slow.next != null) {
56             slow = slow.next;
57             if(pre.val != slow.val) return false;
58             pre = pre.next;
59         }
60         return true;
61     }
62 
63 }

Reference:

1. http://bookshadow.com/weblog/2015/07/10/leetcode-palindrome-linked-list/

2. http://www.cnblogs.com/grandyang/p/4635425.html