题目
请判断一个链表是否为回文链表。
程序核心思想
- 栈结构 时间O(n) 空间O(n)
把链表所有的节点入栈，然后遍历一个，出栈一个，如果值都能对上，那么是回文链表。 - 栈结构 时间O(n) 空间O(n/2)
先遍历一遍得到节点总数，然后入栈一半的节点，然后遍历剩下的节点，同时出栈，如果值能对上，那么是回文链表。
先遍历得到节点总数这一步也可以优化，可以通过快慢指针，慢指针走一步，快指针走两步，由此得到链表的中部位置。 - 不用栈 时间O(n) 空间O(1)
先用快慢指针，快指针走两步，慢指针走一步，当快指针走完时，慢指针来到中点。然后把后半段逆序，然后通过两个指针，一个从头一个从尾开始遍历，直到中点，如果全部相同则true，否则是false，最后再把逆序的后半段还原回去。
下面的三个代码分别代表了第二和第三种方法，第二种方法写了原始版和快慢指针优化版，第三种方法没有还原回去，还原的方法很简单，题目这部分不检测，我就没写。
Tips
快指针能走两步吗？fast.next != null && fast.next.next != null
用这句话来保证。
代码
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
import java.util.Stack;
class Solution {
public boolean isPalindrome(ListNode head) {
Stack<Integer> stack = new Stack<Integer>();
ListNode a = head;
int count = 0;
while(a != null){
a = a.next;
count++;
}
a = head;
for(int i = 0; i < count / 2; i++){
stack.push(a.val);
a = a.next;
}
if(count % 2 != 0){
a = a.next;
}
while(!stack.empty()){
if(a.val != stack.pop()){
return false;
}
a = a.next;
}
return true;
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
import java.util.Stack;
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null) return true;
Stack<Integer> stack = new Stack<Integer>();
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
stack.push(slow.val);
slow = slow.next;
fast = fast.next.next;
}
if(fast.next != null){
stack.push(slow.val);
}
slow = slow.next;
while(slow != null){
if(slow.val != stack.pop()){
return false;
}
slow = slow.next;
}
return true;
}
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
import java.util.Stack;
class Solution {
public boolean isPalindrome(ListNode head) {
if(head == null) return true;
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null){
slow = slow.next;
fast = fast.next.next;
}
ListNode b = slow;
ListNode c = slow;
if(slow.next != null){
b = slow.next;
}else{
return true;
}
if(b.next != null){
c = b.next;
}else{
if(head.val == b.val) return true;
return false;
}
slow.next = null;
while(c != null){
b.next = slow;
slow = b;
b = c;
c = c.next;
}
b.next = slow;
while(b != null && head != null){
if(b.val != head.val) return false;
b = b.next;
head = head.next;
}
return true;
}
}
