題目

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?

Subscribe to see which companies asked this question

---

思路

我的思路

想了半天沒(méi)有想出空間為1的解法，就用了最先考慮到的數(shù)據(jù)結(jié)構(gòu)棧來(lái)實(shí)現(xiàn)了。首先定義兩個(gè)快慢指針，從頭開(kāi)始遍歷，將慢指針壓進(jìn)棧內(nèi)，當(dāng)快指針走到尾時(shí)，慢指針指向的就確定了中間位置。然后慢指針繼續(xù)前進(jìn)，同時(shí)和棧頂元素進(jìn)行比較，如果不相等則返回false。

Hot 解法

開(kāi)始都是使用快慢指針確定了中間位置，然后它實(shí)現(xiàn)了一個(gè)翻轉(zhuǎn)鏈表的操作，將慢指針還未走過(guò)的鏈表翻轉(zhuǎn)了，然后對(duì)翻轉(zhuǎn)的鏈表和從頭開(kāi)始的鏈表進(jìn)行比較。

---

代碼

我的代碼

bool isPalindrome(ListNode* head) {if (!head) return true;stack<ListNode*> st;ListNode* fast=head;ListNode* slow=head;while (fast&&fast->next){st.push(slow);fast=fast->next->next;slow=slow->next;}if (fast) slow=slow->next;while (!st.empty() && slow->val==st.top()->val){st.pop();slow=slow->next;}return st.empty();}

Hot解法

bool isPalindrome(ListNode* head) {if(head==NULL||head->next==NULL)return true;ListNode* slow=head;ListNode* fast=head;while(fast->next!=NULL&&fast->next->next!=NULL){slow=slow->next;fast=fast->next->next;}slow->next=reverseList(slow->next);slow=slow->next;while(slow!=NULL){if(head->val!=slow->val)return false;head=head->next;slow=slow->next;}return true;}ListNode* reverseList(ListNode* head) {ListNode* pre=NULL;ListNode* next=NULL;while(head!=NULL){next=head->next;head->next=pre;pre=head;head=next;}return pre;}

---

鏈表翻轉(zhuǎn)

鏈表翻轉(zhuǎn)就是一道比較經(jīng)典的題目，此處是一個(gè)O（1）的實(shí)現(xiàn)。最重要最需要注意的兩個(gè)地方是提前保存下一個(gè)節(jié)點(diǎn)（next）和保存翻轉(zhuǎn)后的頭結(jié)點(diǎn)（prev）。

ListNode* reverseList(ListNode* head) {ListNode* pre=NULL;ListNode* next=NULL;while(head!=NULL){next=head->next;head->next=pre;pre=head;head=next;}return pre;}

記憶小技巧：在while循環(huán)里一共四句話，最開(kāi)始當(dāng)然是要提前保存正常順序下的下一個(gè)節(jié)點(diǎn)，可以發(fā)現(xiàn)它們都是收尾相接的，最后移動(dòng)head到保存好的next節(jié)點(diǎn)。

總結(jié)

以上是生活随笔為你收集整理的【LeetCode】234. Palindrome Linked List的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。