C++ O(n) time recursive version.

  • 2
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;
        bool flag = true;
        recur_pal(head, head->next, flag);
        return flag;
    void recur_pal(ListNode *&head, ListNode *tail, bool &flag) {
        if (head == tail || head == tail->next) return;
        if (tail->next) {
            recur_pal(head, tail->next, flag);
        if (head->val != tail->val) { flag  = false; return;}
            head = head->next;

  • 6

    I think this is O(n) space (recursion stack)

  • 0

    though use the recursive exhaust many of space ,but expand views ....thanks a lot

Log in to reply

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