
Introduction
In this blog, we will discuss a linked list problem that has been asked frequently in Interviews.
The problem is to find the Length of the most extended palindrome list in a linked list using O(1) extra space.
I am starting with what is a linked list.
It is an ordered set of elements, each holding data and a link containing the address to the next element.
To know more about the linked list, refer here.
We are now coming to the question.
We are given N elements in a linked list, and we are asked to find the Length of the most extended palindrome list in a linked list using O(1) extra space.
For example, the given list is:
The most extended palindromic list here is 2->4->3->4->2.
Length=5
Also see, Data Structures
Approach
Now we will discuss the approach to find the Length of the most extended palindrome list in a linked list using O(1) extra space.
Declare the Node structure and write the function to create and return the node.
⬇
Declare and define a function to return common elements in a list.
⬇
Declare function to return the length of the longest palindromic sublist.
- Start looping till the end of the linked list.
- Reverse each time the elements from head to the current value.
- If we encounter an odd length palindromic sublist, our result will be 2*count of common elements + 1. This 1 has been added to include the current element as well.
- If we encounter an even length palindromic sublist, our result will be 2*count of common elements. We multiplied by 2 because common elements from both lists must be considered.
- Update previous and current elements for the next iteration.
⬇
Return result.
Time Complexity = O(n²).
Since in the worst case, two traversals is needed.
Space Complexity = O(1).
Recommended Topic, Floyds Algorithm
Dry Run on a sample test
Say our list is 2->4->3->4->2->15.
previous=NULL, current=head.(head is the starting position i.e: 2)
So the first list formed will be 2. (on reversing 2, it remains the same.)
The second list formed will be 4->3->4->2->15.
Common element = 0.
The next step does not include a current element(4),
Now, the first list formed will be 2. (on reversing this, we get the same.)
The second list formed will be 3->4->2->15.
Common element = 0.
Next step,
Now, the first list formed will be 2->4. (on reversing this, we get 4->2.)
The second list formed will be 3->4->2->15.
Common element = 0.
The next step does not include a current element(3),
Now, the first list formed will be 2->4. (on reversing this, we get 4->2.)
The second list formed will be 4->2->15.
Common element = 2.
∴Result=2*2+1=5
Here 2 is multiplied because we have to take care of both lists.
And, 1 is added because we have excluded the current element.
Next step,
Now, the first list formed will be 2->4->3. (on reversing this, we get 3->4->2.)
The second list formed will be 4->2->15.
Common element = 0.
The next step does not include a current element(4),
Now, the first list formed will be 2->4->3. (on reversing this, we get 3->4->2.)
The second list formed will be 2->15.
Common element = 0.
Next step,
The first list formed will be 2->4->3->4. (on reversing this, we get 4->3->4->2.)
The second list formed will be 2->15.
Common element = 0.
Next step not including the current element(2),
The first list formed will be 2->4->3->4. (on reversing this, we get 4->3->4->2.)
The second list formed will be 15.
Common element = 0.
Next step,
Now, the first list formed will be 2->4->3->4->2. (on reversing this, we get 2->4->3->4->2.)
The second list formed will be 15.
Common element = 0.
And so on.
Maximum common element found=5.
So, return 5.
Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try.
And solve some related problems on the linked list.
Some Commonly Asked Problems On Linked List
Pseudocode
Algorithm
___________________________________________________________________
procedure maxPalindrome( Node *head ):
___________________________________________________________________
1. result=0
Node *prev = NULL, *curr = head;
2. Begin loop and continue till curr->next==NULL
3. Node *next = curr->next;
curr->next = prev;
4. result = max(result, 2*countCommon(prev, next)+1);
5. result = max(result, 2*countCommon(curr, next));
6. prev = curr;
curr = next;
7. End loop and return result.
end procedure
___________________________________________________________________
Implementation in C++
// Length of the most extended palindrome list in a linked list using O(1) extra space
#include<bits/stdc++.h>
using namespace std;
//declaring the structure of the linked list
struct Node {
int data;
struct Node * next;
};
// function used for keeping track of the common(exact similar) elements
int countCommon(Node * a, Node * b) {
int count = 0;
// loop to calculate length of common elements
for (; a && b; a = a -> next, b = b -> next)
// incrementing the count for same values
if (a -> data == b -> data)
++count;
else
break;
return count;
}
// Returns length of the longest palindrome sublist
int maxPalindrome(Node * head) {
int result = 0;
Node * prev = NULL, * curr = head;
// looping till the end of the linked list
while (curr) {
// The sublist found is reversed.
Node * next = curr -> next;
curr -> next = prev;
// checking for odd length palindrome by finding longest common list elements beginning from prev and from next
result = max(result, 2 * countCommon(prev, next) + 1);
// checking for even length palindrome by finding longest common list elements beginning from curr and from next
result = max(result, 2 * countCommon(curr, next));
// updating prev and curr for next iteration
prev = curr;
curr = next;
}
return result;
}
//function to create a new list node
Node * newNode(int key) {
Node * temp = new Node;
temp -> data = key;
temp -> next = NULL;
return temp;
}
int main() {
Node * head = newNode(2);
head -> next = newNode(4);
head -> next -> next = newNode(3);
head -> next -> next -> next = newNode(4);
head -> next -> next -> next -> next = newNode(2);
head -> next -> next -> next -> next -> next = newNode(15);
cout << maxPalindrome(head) << endl;
return 0;
}
Output:
Input: 2->4->3->4->2->15
Output: 5
Complexity Analysis
Time Complexity: O(n²).
Analyzing Time Complexity:
In the worst case, all elements are to be traversed twice.O(n^2)
Space complexity: O(1) since no extra variable is used.
Check out this problem - Reverse Nodes In K Group
You can also read about Palindrome Number in Python here.