Simple recursive C++ solution in O(n) time.


  • 0
    A
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if(head == NULL) return true;
            
            if(check(head,head)) {
                return true;
            }
            return false;
        }
        
        ListNode* check(ListNode* head,ListNode* end) {
            ListNode* start;
            
            if(end->next) {
                start = check(head,end->next); //Go till end node
                if(start == NULL){ //Return null if mismatch found in between
                    return NULL;
                }
            } else {
                start = head; //start is head when end is reached
            }
            if(start->val == end->val) {
                if(start->next == NULL) {
                    //start reached end, return something non null
                    return head;
                }
                return start->next; // next node from start should be compared with next node from end
            } else {
                return NULL; //mismatch found
            }
        }
    };

  • 0
    A

    recursion nice algo


  • 0
    S

    Recursion leads to O(n) space(I am not sure O(n) or O(logn), but i am sure if you use recursion, the space complexity is certainly not O(1))


Log in to reply
 

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