C++ time limit exceeded


  • 0
    A

    Hi,

    I am trying to solve this problem:

    • I find the length of the list.

    • I reverse the second half.

    • I compare the first half with the second one.
      Here is my implementation. I get TLE but apparently my program stops (I've put some printf to test it).

      class Solution {
      private:
      int getLen(ListNode *head) {
      ListNode *current = head;
      int num = 0;
      while (current) {
      ++num;
      current = current->next;
      }
      return num;
      }

        ListNode* getLast(ListNode *head) {
            ListNode *current = head;
            if (current == NULL) {
                return NULL;
            }
            while (current->next) {
                current = current->next;
            }
            return current;
        }
        void reverse(ListNode *head, int N) {
            ListNode *current = head;
            while (N--) {
                current = current->next;
            }
            ListNode *aux = current->next;
            while (aux) {
                ListNode *temp = aux -> next;
                aux -> next = current;
                current = aux;
                aux = temp;
            }
        }
        bool solve(ListNode *head, ListNode *last, int N) {
            ListNode *left = head;
            ListNode *right = last;
            while (N--) {
                cout << N << "\n";
                cout << "left = " << left->val << "...right = " << right->val << "\n";
                if (left->val != right->val) {
                    return false;
                }
                left = left->next;
                right = right->next;
            }
            return true;
        }
      

      public:
      bool isPalindrome(ListNode* head) {
      cout << "Here\n";
      int N = getLen(head);
      cout << "N = " << N<< "\n";
      ListNode *last = getLast(head);
      cout << "getLast\n";
      if (last == nullptr) {
      return true;
      }
      if (N/2 == 0) {
      if (head->next) {
      return head->val == head->next->val;
      }
      return true;
      }
      reverse(head, N - N/2);
      cout << "reverse\n";

            return solve(head, last, N/2);
        }
      

      };
      For the input 1->2->2->1
      The output is:

      Here
      N = 4
      getLast
      reverse
      1
      left = 1...right = 1
      0
      left = 2...right = 2

    Any hint is useful.
    Many thanks,
    Ioana


  • 0
    G

    I tried the same way and also got TLE.


  • 0
    M

    I did it in a similar way and passed the test.

    class Solution {
    public:
        bool isPalindrome(ListNode* head) {
            if(NULL == head || NULL == head->next) return true;
            int num_nodes = 0;
            ListNode* i_node = head;
            while(NULL != i_node){
                num_nodes++;
                i_node = i_node->next;
            }
            int left_end_idx, right_start_idx;
            if(0 == num_nodes%2){
                left_end_idx = num_nodes/2 - 1;
                right_start_idx = num_nodes/2;
            }
            else{
                left_end_idx = num_nodes/2 - 1;
                right_start_idx = num_nodes/2 + 1;
            }
            
            ListNode* left_end_node, *right_start_node, *end_node;
            
            int node_counter=0;
            i_node = head;
            while(NULL != i_node){
                if(node_counter == left_end_idx) left_end_node = i_node;
                if(node_counter == right_start_idx) right_start_node = i_node;
                if(node_counter == num_nodes-1) end_node = i_node;
                i_node = i_node->next;
                node_counter++;
            }
            
            flip_list(right_start_node);
            
            ListNode* j_node = end_node;
            i_node = head;
            for(int i=0; i<=left_end_idx; i++){
                if(i_node->val != j_node->val) return false;
                i_node = i_node->next;
                j_node = j_node->next;
            }
            
            flip_list(end_node);
            return true;
        }
        
        void flip_list(ListNode* head){
            if(NULL == head || NULL == head->next) return;
            ListNode* node1 = head->next;
            ListNode* node2 = node1->next;
            head->next = NULL;
            while(NULL != node2){
                node1->next = head;
                head = node1;
                node1 = node2;
                node2 = node2->next;
            }
            node1->next = head;
        }
    };

  • 0
    G

    When you reverse the list, you should cut them off. say the list is [1, 2, 3, 4, 5]. After the reverse, 3 will be the last in the first half, but it's next value still points to 4! And 4's next value (which is supposed to be NULL) is still 5. So when you compare, you will go to a dead loop there.


Log in to reply
 

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