My solution status is time limit exceeded, please help


  • 0
    Z

    bool isPalindrome(ListNode* head) {
    if (head == NULL || head->next == NULL){
    return true;
    }

    	ListNode* fast = head;
    	ListNode* slow = head;
    	while (fast->next != NULL && fast->next->next != NULL){
    		slow = slow->next;
    		fast = fast->next->next;
    	}
    
        //to make fast be the last node.
    	if (fast->next != NULL){
    		fast = fast->next;
    	}
    
    	//reverse the rear half of the List
    	ListNode* mid = slow;
    	ListNode* pre = NULL;
    	ListNode* next = NULL;
    	if (mid->next != NULL){
    		next = mid->next;
    	}
    	else {
    		return true;
    	}
    	while (next != NULL){
    		pre = mid;
    		mid = next;
    		next = next->next;
    		mid->next = pre;
    	}
    
        //fast here equals to last.
    	while (head != fast && head->next != fast){
    		if (head->val != fast->val){
    			return false;
    		}
    		head = head->next;
    		fast = fast->next;
    	}
    	return head->val == fast->val;
    }

  • 0
    H

    The driver internally traverses the list, so if your list has a circle, it will cause infinite loop.
    You make a circle in your reversing part.

    In the first loop, you are setting

    slow->next->next = slow;
    

    and thus cause the infinite loop.


  • 0
    Z

    THX for your reply!
    I restore the next position with "next"
    so
    slow->next->next = slow;
    won't make a circle.
    For more information, [1,2] causes time limit exceeded problem.
    BTW, [1,2] passes in my own compiler vs2013.


  • 0
    H

    Hello, you may want to traverse and print the value at the end of your vs2013 program to check where is the circle. By the way, the way you update the node would be a little bit confusing. In the loop, you update the value mid before using it in mid->next = pre, making the logic a little bit unclear.


Log in to reply
 

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