234.回文链表

题目

请判断一个链表是否为回文链表。

程序核心思想

• 栈结构 时间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;
    }
}