Need help with "Palindrome Linked List"-Leetcode

help
1

My this solution is showing TLE . But I dont know why…??? since it is O(n) solution only…PLEASE HELP.
Approach: I iterate through the linked list and form a string of its elements . I form another string with elements in reverse order … if they are same then it is a palindrome ,otherwise not. Have a look at the code,

class Solution {
public:

bool isPalindrome(ListNode* head) {
ListNode*temp=head;
string s1="";
string s2="";
s1+=char('0'+temp->val);
s2+=char('0'+temp->val);
while(temp->next!=NULL)
{
temp=temp->next;
s1+=char('0'+temp->val);
s2=char('0'+temp->val)+s2;


    }
    
    //cout<<s1<<endl;
   // cout<<s2<<endl;
    
    if (s1==s2)
        return true;
    else
        return false;
    
}

};

2

Its giving TLE because of this line-

s2= char('0'+temp->val)+s2;

as it is creating copy of s2 in every iteration.
What you can do is, delete that line and assign s2=s1 outside the loop and reverse it to check palindrome.

1 Like