Sharing my O(n) time and O(1) space c++ solution and O(n) space solution


  • 0
    S

    reverse the half of the linked list and compare one by one can do this in o(n) time and o(1) space.
    But doing this will change the input (well, you can reverse the 2nd half back to keep it original)

    /**
     * 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) {
            ListNode *fast=head,*slow=head,*newHead,*preSlow;
            if(head==NULL || head->next==NULL) return true;
            
            while(fast&&fast->next){
                fast=fast->next->next;
                preSlow=slow;
                slow=slow->next;
            }
            newHead=slow;
            preSlow->next=NULL;
            ListNode *x=NULL,*y=newHead,*z;
            while(y){
                z=y->next;
                y->next=x;
                x=y;
                y=z;
            }
            
            while(head){    // first half of the list node always has equal or less than 1 item than 2nd half, 
                            // so use head not x to check when finished
                if(x->val!=head->val) return false;
                head=head->next;
                x=x->next;
            }
            return true;
        }
    };
    

    This simple solution uses queue and stack, and doesn't change the input, but use O(n) space

       /**
         * 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;
                queue<int> q;
                while(head){
                    st.push(head->val);
                    q.push(head->val);
                    head=head->next;
                }
                while(!st.empty()){
                    if(st.top()!=q.front()) return false;
                    st.pop();
                    q.pop();
                }
                return true;
            }
        };

Log in to reply
 

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