Why my code worked in VS2015, but failed the OJ?


  • 0
    Z

    Hello, everyone!
    Why my code worked in VS2015, but failed the OJ?
    It said Time Limit Exceeded in test case[1,0,0], but in my VS, is was ok.

    I really need help. Thanks.

    #include <iostream>
    using namespace std;
    struct ListNode
    {
    	int val;
    	ListNode *next;
    	ListNode(int x) : val(x), next(NULL) {}
    };
    
    
    //in O(n) time and O(1) space
    
    struct PalindromeHead
    {
    	ListNode* left;
    	ListNode* right;
    };
    
    class Solution 
    {
    public:
    	bool isPalindrome(ListNode* head) 
    	{
    		if (nullptr == head)
    			return false;
    
    		auto count = 0;//Used to record the number of the nodes.
    		auto p = head;
    		while(nullptr != p)//In O(n) time.
    		{
    			++count;
    			p = p->next;
    		}
    
    		if (1 == count)
    			return true;
    
    		p = head;
    		auto q = p->next;
    
    		for (auto i = 0; i < (count - 1) / 2; ++i)
    		{
    			auto temp = q->next;
    			q->next = p;
    			p = q;
    			q = temp;
    		}
    		
    		PalindromeHead* pHead = new PalindromeHead();
    		if (0 == count % 2)
    			pHead->left = p;
    		else
    			pHead->left = p->next;
    		pHead->right = q;
    
    		while (pHead->right)//In O(n) time.
    		{
    			if (pHead->left->val != pHead->right->val)
    			{
    				delete pHead;
    				return false;
    			}
    			
    			//else
    			pHead->left = pHead->left->next;
    			pHead->right = pHead->right->next;
    		}
    
    		delete pHead;
    		return true;
    	}
    };
    
    int main()
    {
    	auto p1 = new ListNode(1);
    
    	auto p2 = new ListNode(0);
    	p1->next = p2;
    	
    	auto p3 = new ListNode(0);
    	p2->next = p3;
    
    
    	Solution s;
    
    	cout<<s.isPalindrome(p1);
    	system("pause");
    	delete p1, p2, p3;
    
    	return 0;
    }

Log in to reply
 

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