A simple 24ms C++ solution


  • 0
    R

    class Solution {

    public:

    bool isPalindrome(ListNode* head) {
    
        if (head == NULL || head->next == NULL) return true;
    
        int n = 0;
        for (ListNode* node = head; node; node = node->next)
            ++n;
    
        ListNode* node = head;
        ListNode* prev = head;
        for (int i = 0; i < (n + 1) / 2; ++i) {
            prev = node;
            node = node->next;
        }
    
        ListNode* tail = NULL;
        while (node) {
            auto temp = node->next;
            node->next = tail;
            tail = node;
            node = temp;
        }
    
        prev->next = tail;
    
        while (tail && tail->val == head->val) {
            tail = tail->next;
            head = head->next;
        }
    
        return tail == NULL;
    }
    

    };

    The length is caculated here. Not so clever as use two pointers to find the middle:)


Log in to reply
 

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