Description:
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?
Link:
https://leetcode.com/problems/palindrome-linked-list/#/description
解題方法：
難點在于如果在O(n) time and O(1) space解決這個問題。
可以用找鏈表中位數(shù)+反轉(zhuǎn)后一半鏈表的方法處理鏈表，然后對比左半段鏈表和右半段鏈表茉稠。
找中位數(shù)用快慢指針非常簡單惫搏，因為實際上是找到右半段鏈表前面一個結(jié)點哀九，所以都不需要考慮奇偶問題忍弛，當(dāng)快指針觸底直接返回慢指針就可以皂岔。
不用額外空間反轉(zhuǎn)鏈表(遞歸)：
輸入?yún)?shù)：右邊結(jié)點的第一個作為curr铃慷，和這個結(jié)點的前一個結(jié)點作為prev单芜。
函數(shù)出口：當(dāng)curr->next == NULL時，直接修改curr的next為記錄的前一個節(jié)點犁柜，返回這個節(jié)點也就是反轉(zhuǎn)后的head洲鸠。
函數(shù)體：用一個next記錄curr->next，然后使curr->next = prev；完成一次反轉(zhuǎn)扒腕，將next作為下一次的curr绢淀，現(xiàn)在的curr作為下一次的prev。
Tips:
在反轉(zhuǎn)鏈表時瘾腰，不要把prev初始化為中位數(shù)的那個結(jié)點皆的，這樣最后比較的時候會進(jìn)入死循環(huán)，應(yīng)該把prev初始化為NULL蹋盆。
Time Complexity：
時間：O(N)
空間：O(1)
完整代碼：
bool isPalindrome(ListNode* head)
{
if(head == NULL || head->next == NULL)
return true;
ListNode* median = findMedian(head);
ListNode* rList = reverseList(NULL, median->next);
ListNode* lList = head;
while(rList != NULL)
{
if(rList->val != lList->val)
return false;
rList = rList->next;
lList = lList->next;
}
return true;
}
ListNode* reverseList(ListNode* prev, ListNode* curr)
{
if(curr->next == NULL)
{
curr->next = prev;
return curr;
}
ListNode* N = curr->next;
curr->next = prev;
return reverseList(curr, N);
}
ListNode* findMedian(ListNode* head)
{
ListNode* slow = head;
ListNode* fast = head;
while(fast != NULL)
{
if(fast->next == NULL || fast->next->next == NULL)
return slow;
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
