問題：
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?
大意：
給出一個單鏈表，判斷它是否是回文。
進(jìn)階：
你能在O（n）的時間復(fù)雜度和O（1）的空間復(fù)雜度下來做嗎？
思路：
回文的意思就是正著讀反著讀都是一樣的。
這道題我使用簡單的思路，一個個遍歷鏈表節(jié)點來倒序組成一個新鏈表，然后和舊鏈表一起遍歷看節(jié)點是不是一樣的，如果一樣說明是回文，否則不是。這個方法很簡單，時間復(fù)雜度是O（n），但是空間復(fù)雜度也是O（n），并不符合進(jìn)階的要求。
代碼（Java）：
/**
* 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 newHead = head;
ListNode lastNode = new ListNode(head.val);
while (newHead.next != null) {
newHead = newHead.next;
ListNode newNode = new ListNode(newHead.val);
newNode.next = lastNode;
lastNode = newNode;
}
if (head.val != lastNode.val) return false;
while (head.next != null) {
head = head.next;
lastNode = lastNode.next;
if (head.val != lastNode.val) return false;
}
return true;
}
}
他山之石：
public class Solution {
public boolean isPalindrome(ListNode head) {
ListNode fast = head, slow = head;
Stack<ListNode> stack = new Stack<>();
while(fast != null && fast.next != null){
stack.push(slow);
fast = fast.next.next;
slow = slow.next;
}
// for odd list
if(fast != null){
slow = slow.next;
}
while(slow != null){
if(stack.pop().val != slow.val) return false;
slow = slow.next;
}
return true;
}
}
這個做法跟我的不一樣，使用了快慢兩個標(biāo)記，快的那個只有一個用處，就是以兩倍速度遍歷，引導(dǎo)慢的標(biāo)記到達(dá)鏈表最中心，當(dāng)然這里要根據(jù)鏈表個數(shù)是奇數(shù)還是偶數(shù)來分開判斷，也是看fast是正好跑到最后面還是跑過了來判斷。找到中心后，利用棧存放的數(shù)據(jù)先進(jìn)后出的特性，從中間往兩頭一起遍歷，看遍歷的值是不是都一樣，一樣則是回文，否則不是。這個做法同樣的時間復(fù)雜度是O（n），二空間復(fù)雜度是O（n），因為用到了一個棧。不過速度應(yīng)該比我的要快一半
合集：https://github.com/Cloudox/LeetCode-Record
