題目

請(qǐng)判斷一個(gè)鏈表是否為回文鏈表。

程序核心思想

• 棧結(jié)構(gòu) 時(shí)間O(n) 空間O(n)
  把鏈表所有的節(jié)點(diǎn)入棧睦袖，然后遍歷一個(gè)珊肃，出棧一個(gè)，如果值都能對(duì)上馅笙，那么是回文鏈表伦乔。
• 棧結(jié)構(gòu) 時(shí)間O(n) 空間O(n/2)
  先遍歷一遍得到節(jié)點(diǎn)總數(shù)，然后入棧一半的節(jié)點(diǎn)董习，然后遍歷剩下的節(jié)點(diǎn)烈和，同時(shí)出棧，如果值能對(duì)上皿淋，那么是回文鏈表招刹。
  先遍歷得到節(jié)點(diǎn)總數(shù)這一步也可以優(yōu)化恬试，可以通過快慢指針，慢指針走一步疯暑，快指針走兩步训柴，由此得到鏈表的中部位置。
• 不用棧 時(shí)間O(n) 空間O(1)
  先用快慢指針妇拯，快指針走兩步幻馁，慢指針走一步，當(dāng)快指針走完時(shí)越锈，慢指針來到中點(diǎn)仗嗦。然后把后半段逆序，然后通過兩個(gè)指針甘凭，一個(gè)從頭一個(gè)從尾開始遍歷稀拐，直到中點(diǎn)，如果全部相同則true对蒲，否則是false钩蚊，最后再把逆序的后半段還原回去。

下面的三個(gè)代碼分別代表了第二和第三種方法蹈矮，第二種方法寫了原始版和快慢指針優(yōu)化版砰逻，第三種方法沒有還原回去，還原的方法很簡(jiǎn)單泛鸟，題目這部分不檢測(cè)蝠咆，我就沒寫。

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;
    }
}