Clean C++ Code on 19ms O(n) Run Time and O(1) Space


  • 0
    M

    First loop reverse the half of the linked list, then the second for compare.

    Suppose the linked list is A->B->C->D for even length. Then pre = B and head = C
    .
    Suppose the linked list is A->B->C->D->E for odd length. Then pre = B and head = C. We need head = head->next to omit the C because C is the middle.

    Here is the code:

    /**
     * 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) {
            
            if(!head || !head->next) return true;
            
            ListNode *pre = NULL, *fast = head;
            
            while(fast && fast->next) {
                fast = fast->next->next;
                ListNode *next = head->next;
                head->next = pre;
                pre = head;
                head = next;
            }
            
            if(fast) head = head->next;
            
            while(pre && head) {
                if(pre->val != head->val) return false;
                pre = pre->next;
                head = head->next;
            }
            
            return true;
        }
    };
    

Log in to reply
 

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