Finding palindromes in a linked list

Question

This is an interview question(again).

Given a singly connected linked list, find the largest palindrome in the list. (You may assume the length of the palindrome is even)

The first approach I made was using a stack - we traverse over the list from the start and keep pushing in the letters. Whenever we find the letter on the top of the stack is same as the next letter on the linked list, start popping(and incrementing the linked list pointer) and set a count on the number of letters that matches. After we find a mismatch, push back all the letters that you popped from the stack, and continue your pushing and popping operations. The worst case complexity of this method would be O(n2) e.g. when the linked list is just a string of the same letters.

To improve on the space and time complexity(by some constant factors), I proposed copying the linked list to an array and finding the largest sized palindrome in the array which again takes O(n2) time complexity and O(n) space complexity.

Any better approach to help me with? :(

you can look at http://stackoverflow.com/questions/7043778/longest-palindrome-in-a-string-using-suffix-tree/7044687#7044687 or http://stackoverflow.com/questions/1115001/write-a-function-that-returns-the-longest-palindrome-in-a-given-string But I won't say it's a duplicate since these 2 doesn't talk about linked list — Ricky Bobby, Aug 13 '11 at 07:52
"(You may assume the length of the palindrome is even)" you never use this ? why do you think it's important ? — Ricky Bobby, Aug 13 '11 at 07:54
"push back all the letters that you popped from the stack" - that's not so trivial, and your stack would require O(n) space. — H H, Aug 13 '11 at 08:28
@Ricky: Even sized palindrome implies that the next character to be matched must be the same as the charater on the top of the stack. Had it been an odd sized palindrome, there would be many more combinations to check ( for example, assuming that the element on the top of the stack is the middle element of the odd sized palindrome and so, pop the topmost element and then, begin checking the stack and the remaining part of the string. — letsc, Aug 13 '11 at 13:07

rumpel · Answer 1 · 2011-09-06T10:07:59.963

One could come up with a O(n²)-algorithm with O(1) space complexity as follows:

Consider f→o→b→a→r→r→a→b:

Walk through the list reversing the links while visiting. Start with x=f and y=f.next:

set x.next = null
```
f o→b→a→r→r→a→b
^ ^
|  \
x   y
```
and check for how many links both lists (x and y) are equal.
Now continue. (tmp=y.next, y.next=x, x=y, y=tmp) E.g. in the second step, it will yield f←o b→a→r→r→a→b, with x=o and y=b, now you check again if it's a palindrome and continue:
f←o←b a→r→r→a→b
f←o←b←a r→r→a→b
f←o←b←a←r r→a→b yay :)
etc.

If you need to restore the list again, reverse it again in O(n)

score 4 · Answer 2 · answered Sep 02 '11 at 02:24

This is a well analyzed problem with O(N) time complexity.

You can reverse the original string(let's say str and str_reversed)

Then the problem is transformed to: find the longest common substring in str and str_reversed.

An O(N) approach is building a suffix tree(O(N)) with constant time lowest common ancestor retrieval.

phimuemue · Answer 3 · 2011-08-13T09:49:24.950

If you copy the lists to an array, the following could be useful: Since we consider only even-length-palindromes, I assume this case. But the technique can be easily extended to work wich odd-length-palindromes.

We store not the actual length of the palindrome, but half the length, so we know how many characters to the left/right we can go.

Consider the word: aabbabbabab. We are looking for the longest palindrome.

a a b b a b b a b a b (spaces for readability)
°^°                   start at this position and look to the left/right as long as possible,
 1                    we find a palindrome of length 2 (but we store "1")
                      we now have a mismatch so we move the pointer one step further
a a b b a b b a b a b
   ^                  we see that there's no palindrome at this position, 
 1 0                  so we store "0", and move the pointer
a a b b a b b a b a b
  ° °^° °             we have a palindrome of length 4, 
 1 0 2                so we store "2"
                      naively, we would move the pointer one step to the right,
                      but we know that the two letters before pointer were *no*
                      palindrome. This means, the two letters after pointer are
                      *no* palindrome as well. Thus, we can skip this position
a a b b a b b a b a b
         ^            we skipped a position, since we know that there is no palindrome
 1 0 2 0 0            we find no palindrome at this position, so we set "0" and move on
a a b b a b b a b a b
      ° ° °^° ° °     finding a palindrome of length 6,
 1 0 2 0 0 3 0 0      we store "3" and "mirror" the palindrome-length-table
a a b b a b b a b a b
                 ^    due to the fact that the previous two positions hold "0", 
 1 0 2 0 0 3 0 0 0    we can skip 2 pointer-positions and update the table
a a b b a b b a b a b
                   ^  now, we are done
 1 0 2 0 0 3 0 0 0 0

This means: As soon as we find a palindrome-position, we can infer some parts of the table.

Another example: aaaaaab

a a a a a a b
°^°
 1

a a a a a a b
° °^° °
 1 2 1        we can fill in the new "1" since we found a palindrome, thus mirroring the
              palindrome-length-table
a a A A a a b (capitals are just for emphasis)
     ^        at this point, we already know that there *must* be a palindrome of length
 1 2 1        at least 1, so we don't compare the two marked A's!, but start at the two 
              lower-case a's

My point is: As soon as we find palindromes, we may be able to mirror (at least a part of) the palindrome-length table and thus infer information about the new characters. This way, we can save comparisons.

score 0 · Answer 4 · edited Nov 22 '13 at 07:24

I did it by using recursion in O(n) time. I am doing this by,

suppose we have a source linked list, now copy the entire linked list to other linked list i.e. the target linked list;
now reverse the target linked list;
now check if the data in the source linked list and target linked list are equal, if they are equal they are palindrome, otherwise they are not palindrome.
now free the target linked list.

Code:

#include<stdio.h>
#include<malloc.h>

struct node {
    int data;
    struct node *link;
};

int append_source(struct node **source,int num) {
    struct node *temp,*r;
    temp = *source;
    if(temp == NULL) {
        temp = (struct node *) malloc(sizeof(struct node));
        temp->data = num;
        temp->link = NULL;
        *source = temp;
        return 0;
    }
    while(temp->link != NULL) 
        temp = temp->link;
    r = (struct node *) malloc(sizeof(struct node));
    r->data = num;
    temp->link = r;
    r->link = NULL;
    return 0;
}

int display(struct node *source) {
    struct node *temp = source;
    while(temp != NULL) {
        printf("list data = %d\n",temp->data);
        temp = temp->link;
    }
    return 0;
}

int copy_list(struct node **source, struct node **target) {
    struct node *sou = *source,*temp = *target,*r;
    while(sou != NULL) {
        if(temp == NULL) {
            temp = (struct node *) malloc(sizeof(struct node));
            temp->data = sou->data;
            temp->link = NULL;
            *target = temp;
        }
        else {
            while(temp->link != NULL) 
                temp = temp->link;
            r = (struct node *) malloc(sizeof(struct node));
            r->data = sou->data;
            temp->link = r;
            r->link = NULL;
        }
        sou = sou->link;
    }
    return 0;
}

int reverse_list(struct node **target) {
    struct node *head = *target,*next,*cursor = NULL;
    while(head != NULL) {
        next = head->link;
        head->link = cursor;
        cursor = head;
        head = next;
    }
    (*target) = cursor;
    return 0;
}

int check_pal(struct node **source, struct node **target) {
    struct node *sou = *source,*tar = *target;
    while( (sou) && (tar) ) {
        if(sou->data != tar->data) {
            printf("given linked list not a palindrome\n");
            return 0;
        }
        sou = sou->link;
        tar = tar->link;
    }
    printf("given string is a palindrome\n");
    return 0;
}

int remove_list(struct node *target) {
    struct node *temp;
    while(target != NULL) {
        temp = target;
        target = target->link;
        free(temp);
    }
    return 0;
}

int main()
{
    struct node *source = NULL, *target = NULL;
    append_source(&source,1);
    append_source(&source,2);
    append_source(&source,1);
    display(source);
    copy_list(&source, &target);
    display(target);
    reverse_list(&target);
    printf("list reversed\n");
    display(target);
    check_pal(&source,&target); 
    remove_list(target);
    return 0;
}

score 0 · Answer 5 · answered Aug 13 '11 at 09:16

Here is a O(n^2) algorithm:

Convert the list to a doubly linked list
To have an even length palindrome you need to have two same letters next to each other. So iterate over each each pair of neighboring letters (n-1 of them) and on each iteration, if the letters are identical, find the largest palindrome whose middle letters are these two.

score -2 · Answer 6 · answered May 23 '12 at 16:35

-2

First find the mid point of the linked list, for this traverse through the linked list and count the number of nodes.

Let's say number of nodes is N, mid point will be N/2.

Now traverse till the mid-point node and start reversing the linked list till the end which can be done in place with O(n) complexity.

Then compare the elements from start to midpoint with elements from mid-point to last if they all are equal, string is a palindrome, break otherwise.

Time Complexity :- O(n)

Space Complexity :- O(1)

answered May 23 '12 at 16:35

Aditya Agarwal

1
1

That tests if the entire list is a palindrome, which was not the question. – hammar Oct 21 '12 at 00:23
Yes you are right hammar. I am sorry didn't read the question properly. – Aditya Agarwal Apr 27 '15 at 07:01

Finding palindromes in a linked list

6 Answers6