My first 'beats 100%' solution,:D


  • 0
    X
    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
    		if (!head || !head->next)
    			return true;
    		auto cur1 = head, cur2 = head;
    		while (cur2->next && cur2->next->next) {
    			cur1 = cur1->next;
    			cur2 = cur2->next->next;
    		}//find the 'middle' node.
    		ListNode *pre = cur1;
    		ListNode *cur = cur1->next;
    		cur1->next = nullptr;//really important,TLE happened without it
    		while (cur) {
    			auto next = cur->next;
    			cur->next = pre;
    			pre = cur;
    			cur = next;
    		}//reverse
    		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.