basic solution and follow up


  • 0
    N

    Time : O(N)
    Space: O(N)

    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if (head == nullptr)
                return true;
            int i, j;
            vector<int> res;
            ListNode *cur = head;
            while (cur) {
                res.push_back(cur->val);
                cur = cur->next;
            }
            
            i = 0;
            j = res.size() - 1;
            while (i < j) {
                if (res[i] != res[j]) {
                    return false;
                }
                i++;
                j--;
            }
            
            return true;
        }
    };
    

    Time O(N)
    Space O(1)

    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if (head == nullptr || head->next == nullptr)
                return true;
            ListNode *slow = head, *fast = head, *cur1 = head, *cur2;
            
            while (fast->next && fast->next->next) {
                slow = slow->next;
                fast = fast->next->next;
            }
            
            cur2 = reverse(slow->next);
            while (cur1 && cur2) {
                if (cur1->val != cur2->val)
                    return false;
                cur1 = cur1->next;
                cur2 = cur2->next;
            }
            
            return true;
        }
        
        ListNode* reverse(ListNode* head) {
            ListNode* prev = NULL, *cur = head, *follow;
            while (cur) {
                follow = cur->next;
                cur->next = prev;
                prev = cur;
                cur = follow;
            }
            
            return prev;
        }
    };
    

Log in to reply
 

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