Share my C++ solution, O(n) time, O(1) space


  • 7
    I
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true;
        ListNode *slow = head, *fast = head->next, *prev = NULL;
        while (true) {
    	    if (!fast->next) {
    		    fast = slow->next;
    		    slow->next = prev;
    		    break;
    	    } else if (!fast->next->next) {
    		    fast = slow->next->next;
    		    slow->next = prev;
    		    break;
    	    } else {
    		    fast = fast->next->next;
    		    ListNode *temp = slow->next;
    		    slow->next = prev;
    		    prev = slow;
    		    slow = temp;
    	    }
        }
        while (slow && fast) {
    	    if (slow->val != fast->val) return false;
    	    slow = slow->next;
    	    fast = fast->next;
        }
        return true;
    }

  • 0
    Z

    what a nice solution! I've learned.


Log in to reply
 

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