C++ time limit exceeded

• 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) {
}
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

• I tried the same way and also got TLE.

• 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;
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;
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;
}

if(NULL == head || NULL == head->next) return;
ListNode* node1 = head->next;
ListNode* node2 = node1->next;
while(NULL != node2){