CODEWITHSUNDEEP
algorithmdata-structures
princess of persia
princess of persia

Reputation: 2232

In a singly linked list of integers, find if the list is a palindrome

I have written a function for this in C which takes in head of the list and returns 1 if the list is a palindrome else it returns 0. Please let me know if there are any mistakes or if theres a better way to do it, I am not sure if corner cases have been handled

Node * end = head;
int isListPalindrome(Node * head)
{
    int i = 1;
    int mid, pal;
    i++;
    if (head -> next == NULL)
    {
    end = head;

    if(end-> data != head -> data)
        {
            printf("Not a Palindrome");
            return 0;
        }
    else i--;

    mid = i/2;
    return 1;
}

pal = isListPalindrome(head ->next);
end = end ->next;
i --;

if ((i >= mid) && !pal)
{
    printf("Not a Palindrome");
    return 0;
}

else printf("Its a Palindrome");
return pal;

}

Upvotes: 1

Views: 1893

Answers (1)

Shankhoneer Chakrovarty
Shankhoneer Chakrovarty

Reputation: 685

Initialize two pointers: slow and fast pointers, increment the slow by one and fast by two (like floyd cycle finding algorithm) at every step push the data pointed by slow pointer to a stack, as soon as fast pointer becomes NULL break the loop. Start another loop while slow is not null and stack is not NULL compare the stack.top with data pointed by slow, if there is any mismatch the list is not palindrome.

For example:

1->2->2->1

Slow points to 0th pos
Fast points to 0th pos

1st Step:
Slow points to 1st pos
Fast points to 2nd pos
Stack has 1

2nd step
Slow points to 2nd pos
Fast goes to NULL
Stack has 1->2

Another loop while slow!=NULL

1st step
slow points to 3rd pos(Data=2 stack top=2, Match so pop from stack)
stack has 1

2nd step

slow points to 4th place (data =1 stack top =1 Match so pop from stack)
stack=NULL

break out
Since everything matches so is a palindrome

ALTERNATIVE,

Reverse the list from first node till the node before the slow pointer. So here it will be

1<-2 2->1
   | |
head slow
 of
 the first half of the linked list

Now start comparing.

Upvotes: 7

Related Questions