My code:
import java.util.Stack;
/**
* 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 slow = head;
ListNode fast = head;
Stack<Integer> s = new Stack<Integer>();
s.push(slow.val);
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
s.push(slow.val);
}
if (fast.next == null)
s.pop();
slow = slow.next;
while (slow != null) {
int val = slow.val;
if (val != s.pop())
return false;
slow = slow.next;
}
return true;
}
}
My test result:
这道题目我一开始想用异或来做，后来发现错的，即使一个数字出现了偶数次，不代表他的位置是对称的，不一定是回文。
网上找了做法。
挺经典的。
先走到中间，将之前的值压在栈里面。
然后再往右走，将栈中的数据一个个弹出和之后的结点比对。
**
然后这里介绍一个技巧，是我之前完全不知道的。
用快慢指针来找一个链表的中点。
慢指针走一步，快指针走两步，同时每次循环都得判断下，
fast.next != null && fast.next.next != null
同时还有个细节。
如果是奇数个结点，则此时将中间值压入栈中了，事实上没有数字和他对应，所以需要手动弹出。
这是链表的一个小技巧。
还有个小技巧就是，设置 dummy head。 可以简单地通过许多corner case.
**
参考的博客。
http://www.cnblogs.com/grandyang/p/4635425.html
**
总结： 快慢指针找链表中点。栈
**
Anyway, Good luck, Richardo!
My code:
/**
* 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;
}
ArrayList<Integer> al = new ArrayList<Integer>();
ListNode temp = head;
while (temp != null) {
al.add(temp.val);
temp = temp.next;
}
int begin = 0;
int end = al.size() - 1;
while (begin < end) {
if (al.get(begin).intValue() != al.get(end).intValue()) {
return false;
}
begin++;
end--;
}
return true;
}
}
一开始看到回文，首先想到了string。所以想把list 转换成string。但后来发现不对，负数表示会有问题。
这里可以看出，我的思维还是不够严谨，不能提前发现问题！
然后选择使用ArrayList.同样出现了一个问题。我一直不知道哪里错了，直到用eclipse debug才发现。
我的ArrayList 里面存的是 Integer, 比较的时候不能直接 !=
应该， list.get(i).intValue ,取出 int值来进行比较。
下面重写下栈的做法。
/**
* 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;
}
int counter = 1;
Stack<ListNode> s = new Stack<ListNode>();
ListNode slow = head;
ListNode fast = head;
s.push(slow);
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next;
fast = fast.next;
counter += 2;
s.push(slow);
}
if (fast.next != null) {
counter++;
}
if (counter % 2 == 1) {
s.pop();
}
slow = slow.next;
while (slow != null) {
ListNode temp = s.pop();
if (temp.val != slow.val) {
return false;
}
slow = slow.next;
}
return true;
}
}
看之前的做法，的确不用计数器。
然后得思考下，如何才能用O(1)的空间复杂度呢？
/**
* 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 slow = head;
ListNode fast = head;
ListNode p = slow.next;
// find middle, reverse
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
ListNode next = p.next;
p.next = slow;
slow = p;
p = next;
}
if (fast.next == null) {
slow = slow.next;
}
while (slow != null && p != null) {
if (slow.val != p.val) {
return false;
}
slow = slow.next;
p = p.next;
}
return true;
}
}
思路很简单，就是走到中点，将前面的链表反转，然后比较。
问题是！我改变了原链表的结构，这在实际工作中是很危险的！往往传进来的结构都应该是只读的，很容易出错，而且程序大了，根本不知道是哪个类修改了这个结构。而好处，仅仅只是，空间的确少用了很多。
但是， O(n) 空间复杂度，对于现代计算机来说，本身也是可以接受的啊！
Anyway, Good luck, Richardo! -- 08/15/2016
