234. Palindrome Linked List
problem description
Given a singly linked list, determine if it is a palindrome.
Example 1:
Input: 1->2
Output: false
Example 2:
Input: 1->2->2->1
Output: true
Follow up: Could you do it in O(n) time and O(1) space?
algorithm thought
这里主要是找到链表的中点,将链表分成两半,然后匹配是否是回文串。找到中点用快慢指针。使用一个stack来辅助,就只需要一次遍历可的结果
code
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
stack<int> st;
ListNode* fast=head,*slow=head;
while(fast!=NULL&&fast->next!=NULL){
st.push(slow->val);
slow=slow->next;
fast=fast->next->next;
}
if(fast)
slow=slow->next;
while(slow){
if(slow->val!=st.top())
return false;
slow=slow->next;
st.pop();
}
return true;
}
};
algorithm analysis
一次遍历,时间复杂度是O(n),使用栈辅助,空间复杂度也是O(n)
Last updated