Problem: Check if a (extra-large) singly linked list of charcters is a palindrome or not.
Solution1:
The brute force algorithm is to revese the linked list and check if the original and reversed linked lists are equal.
Time Complexity: O(n)
Space Compexity: Not good, as it requires an extra linked list.
Solution 2:
1. Find the middle node of the list: This can be done by looping through the list, using two pointers and incrementing the second pointer by 1 only when the first pointer is increamented by two steps. The second pointer would give the middle node of the list, when the first pointer reaches the end of the linked list.
2. Reverse the first half of the linked list.
3. Check if the first half and the second half of the list are equal.
Time Complexity: O(n)
Space Complexity: Better than the first, as we are using only a single linked ist.
If there is a better algorithm, please add to the comments.
Subscribe to:
Post Comments (Atom)
2 comments:
Code for Solution2:
int IsLinkPalindrome(struct Node *lnk)
{
int s1 =0, s2=0;
struct Node *tmp1 = lnk,*rev = NULL, *tmp2=NULL;
//Find the middle charcter
if (tmp1 == NULL)
return 0;
while (tmp1->next!= NULL)
{
tmp1 = tmp1->next;
s1++;
if (s1%2==0)
s2++;
}
s1++;
//Handle special cases
if (s1==s2)
return 1;
if (s1==2)
return 0;
if (s1%2 ==0)
s2++;
//Reverse the first half
rev =RevPartLL(lnk,s2);
//Compare the links
// first = s1;
// second = lnk;
tmp2 = tmp1 = rev;
for (int i =1; i<=s2; i++)
{
tmp2 = tmp2->next;
}
if (s1%2 !=0) tmp2 = tmp2->next;
while (tmp2 != NULL)
{
if (tmp2->c !=tmp1->c)
return 0;
tmp2 = tmp2->next;
tmp1 = tmp1->next;
}
return 1;
}
struct Node * RevPartLL(struct Node *lnk, int n)
{
struct Node *first, *second, *third;
if (lnk == NULL || lnk->next == NULL)
return lnk;
first = lnk;
second = lnk->next;
for (int i=1; inext;
second->next = first;
first = second;
second = third;
}
lnk->next = second;
return first;
}
A minor correction..the special case of s1==2, should be handled this way...
if (lnk->c == lnk->next->c)
return 1;
else return 0;
Post a Comment