234. Palindrome Linked List

發表於 | 分類於

problem

solution

option 1 - iterative
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        // iterative + stack
        stack<int> sta;
        ListNode *slow = head, *fast = head;
        while(fast && fast->next){
            slow = slow->next;
            fast =fast->next->next;
        }
        while(slow){
            sta.push(slow->val);
            slow = slow->next;
        }
        fast = head;
        while(!sta.empty() && fast->val==sta.top()){
            sta.pop();
            fast = fast->next;
        }
        return sta.empty(); 
    }
};
option 2 - recursive
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode *left;
    bool traverse(ListNode *right){
        if(!right) return true;
        
        bool ret = traverse(right->next);
        if(left->val != right->val) return false;
        left = left->next;
        return ret ;
    }
    bool isPalindrome(ListNode* head) {
        // recursive
        left = head;
        return traverse(head);
    }
};

analysis

  • time complexity O(n)
  • space complexity O(1)