C++ using stack, simple and easy understand.


  • 0
    Q
    /**
     * 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> s;
            ListNode* tmp = head;
            int count = 0;
            while(tmp){
                count++;
                tmp = tmp->next;
            }
            if(count==1) return true;
            int half = count/2 + count%2;
            for(int i=1; i<=half;i++){
                s.push(head->val);
                head = head->next;
            }
            if(count%2) s.pop();    // incase of {1,0,0} such cases
            while(head && head->val == s.top()){
                head = head->next;
                s.pop();
            }
            if(!head) return true;
            return false;
        }
    };

  • 0
    G

    I have similar idea about solution. Reverse second half, then compare. However, I got Time Limit Exceeded with input [1,0,0]. Any idea?

    bool isPalindrome(struct ListNode* head) {
    if (head == NULL)
        return true;
    struct ListNode *p=head, *q, *r, *tail=head;
    int len = 1, i;
    while (tail->next != NULL) {
        len++;
        tail = tail->next;
    }
    for (i=0; i<len/2; i++){
        p = p->next;
    }
    // now p is the start of second half
    q = p->next;
    while(q!=NULL){
        r = q->next;
        q->next = p;
        p = q;
        q = r;
    }
    p = head; q = tail;
    for (i=0; i<len/2; i++){
        if (p->val != q->val)
            return false;
        p = p->next; q= q->next;
    }
    return true;
    

    }


  • 0
    Q

    your solution doesn't take where is len/2 into consideration, it should be len/2 + 1 for {1,0,0}
    Then your stack contain 1,0. you have to pop 0, and compare 1 with 0


  • 0
    G

    For {1,0,0}, len==3. So the last for loop runs 1 time, comparing 1 with 0.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.