InterviewSolution
Saved Bookmarks
InterviewSolution
| 1. |
Given a linked list, find the length of the longest palindrome list that appears in that linked list using O(1) extra space. |
|
Answer» The concept is built on reversing a linked list iteratively. We LOOP through the given linked list, reversing each prefix of the linked list one by one from the left. We discover the longest common list beginning with the reversed prefix and the list after the reversed prefix, after reversing a prefix. Time complexity is O(n^2). Implementation: int calcCommon(NODE *x, Node *y){ int cnt = 0; // count common in the list starting // from node x and y while (1) { // increase the count by one for same VALUES if (x->value == y->value) cnt++; else break; x = x->next; y = y->next; } return cnt;}// Returns length of the longest palindrome sublistint maxPalindrome(Node *head){ Node *previous = NULL, *current = head; int answer = 0; // loop running till the end of the linked list while (1) { if(current==NULL) break; // reversed sublist from head to current Node *next = current->next; current->next = previous; // check for odd length palindrome answer = max(result, 2*calcCommon(previous, next)+1); // check for even length palindrome answer = max(result, 2*calcCommon(current, next)); // UPDATE previous and current for next iteration previous = current; current = next; } return answer;} |
|