Find palindromes in a linked list

Question

This is an interview question (again).

Given a single-linked linked list, find the largest palindrome in the list. (You can assume that the length of the palindrome is even)

The first approach I took was to use the stack - we go through the list from the very beginning and continue to press letters. Whenever we find that the letter at the top of the stack matches the next letter in the linked list, start popping up (and increase the index of the linked list) and set the number to the number of letters that matches. After we find the discrepancy, discard all the letters that you pulled from the stack, and continue your actions by clicking and popping up. The worst difficulty of this method is O (n2), for example. when a linked list is just a string of the same letters.

To improve spatial and temporal complexity (with the help of some constant factors), I suggested copying the linked list into an array and finding the largest size palindrome in the array, which again takes the time complexity O (n2) and O (n) space complexity.

Any better approach to help me? :(

Answer 1

You can come up with an O (n²) algorithm with O (1) spatial complexity as follows:

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

Go through the list, changing the links during the visit. Start with x=f and y=f.next :

• set x.next = null

•   fo → b → a → r → r → a → b
   ^ ^
   |  \
   xy 

  and check how many links both lists (x and y) are equal.
• Now go on. ( tmp=y.next , y.next=x , x=y , y=tmp ) For example. in the second stage, it will give f←ob→a→r→r→a→b , with x=o and y=b , now you again check whether it will be a palindrome and continue:
• f←o←ba→r→r→a→b
• f←o←b←ar→r→a→b
• f←o←b←a←rr→a→b yay :)
• and etc.

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

Answer 2

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

• You can change the original string (say str and str_reversed )

Then the task is converted to: find the longest common substring in str and str_reversed .

• The O (N) approach builds a tree of suffixes (O (N)) with a search with a minimum common mineral with constant time.

Answer 3

If you copy the lists into an array, the following may be useful: since we only consider even-palindromes, I assume this case. But the technique can be easily expanded to work with odd palindromes.

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

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

 aabbabbabab (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 aabbabbabab ^ we see that there no palindrome at this position, 1 0 so we store "0", and move the pointer aabbabbabab ° °^° ° 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 aabbabbabab ^ 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 aabbabbabab ° ° °^° ° ° finding a palindrome of length 6, 1 0 2 0 0 3 0 0 we store "3" and "mirror" the palindrome-length-table aabbabbabab ^ 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 aabbabbabab ^ now, we are done 1 0 2 0 0 3 0 0 0 0 

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

Another example: aaaaaab

 aaaaaab °^° 1 aaaaaab ° °^° ° 1 2 1 we can fill in the new "1" since we found a palindrome, thus mirroring the palindrome-length-table aa AA aab (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 the palindromes, we can mirror (at least part) the table of the length of the palindrome and thereby display information about new characters. That way we can keep comparisons.

Answer 4

Here is the O (n ^ 2) algorithm:

• Convert list to doubly linked list

• To have an even-length palindrome, you need to have two identical letters next to each other. So, sort through each pair of adjacent letters (n-1 of them) and at each iteration, if the letters are the same, find the largest palindrome, the middle letters of which are these two.

Answer 5

I did this using recursion in O (n) time. I'm doing it,

• Suppose we have a list associated with the source, now copy the entire linked list to another linked list, i.e. linked list of goals;
• now drag the target list;
• now check if the data from the source-linked list and the target linked list are equal, if they are equal, this is a palindrome, otherwise they are not a palindrome.
• now free the target list.

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

Answer 6

First, find the midpoint of the linked list, for this passage through the linked list and counting the number of nodes.

Let's say the number of nodes is N, the midpoint will be N / 2.

Now go to the middle of the node item and start reversing the linked list to the end, which can be done using O (n) complexity.

Then compare the elements from the beginning to the middle with the elements from the middle to the last, if they are all equal, the line is a palindrome, otherwise it is a gap.

Time complexity: - O (n)

Cosmic complexity: - O (1)