Amazon Interview Question Software Engineer / Developers
Reverse the second half and then check each node:
1>2>3>4>5>4>3>2>1 => 1>2>3>4>5<4<3<2<1
Both above are good and have same logic. 1st one if list is not editable, 2nd if editing allowed.
Nope buddy, thats wrong.
As @gekko says the recursion algo is using an additional array. In the example it uses "int a[100];" and if the node contains some object other than 'int' then this approach would need an array of objects. which is basically worse than iteration.
Instead of the recursion you could simply copy the linked list to an array and check for palindrome iteratively which has same time complexity and lesser space complexity than recursion algo above.
@S: To find whether a Linked list is palindrome, you are
modifying the list, this is not good. If you copy to
another list and check means you are using another data
structure, that is not allowed.
@Anonymous: Copying the list to array is also not allowed.
Because array is also a data structure (Question without
using any data structure)
It's pretty easy to restore the list afterwards, by just reversing the second half again? It's still O(n)
reposting the above code without using arr[100], as this is also a data structure, as per the question it is not allowed to use.
#include "stdafx.h"
#include <iostream>
using namespace std;
int ispalindrome(node*, node**, int&, int, int&);
struct node
{
int data;
struct node *link;
};
int _tmain(int argc, _TCHAR* argv[])
{
struct node *head=NULL, *h1;
h1 = head;
insert(&head, 1);
insert(&head, 2);
insert(&head, 3);
insert(&head, 3);
insert(&head, 2);
insert(&head, 3);
insert(&head, 1);
int k=1;
cout << "Is palindrome: " << ispalindrome(head1, &h1, k) << endl;
}
int ispalindrome(node *head, node**h1, int &flag)
{
int b;
if(head == NULL)
return 0;
b = head->data;
ispalindrome(head->link, a, i, n, flag);
if(b != (*h1)->data)
flag = 0;
(*h1) = (*h1)->link;
return flag;
}
Still here using 2 int variables and 1 node* variable.
Finally got O(n) time and O(1) space solution:
#include "stdafx.h"
#include <iostream>
using namespace std;
void ispalindrome(node*, node**);
struct node
{
int data;
struct node *link;
};
int _tmain(int argc, _TCHAR* argv[])
{
struct node *head=NULL, *h1;
h1 = head;
insert(&head, 1);
insert(&head, 2);
insert(&head, 3);
insert(&head, 3);
insert(&head, 2);
insert(&head, 3);
insert(&head, 1);
int k=1;
ispalindrome(head1, &h1);
if(h1 == NULL)
cout << "YES";
else
cout << "NO";
}
void ispalindrome(node *head, node**h1)
{
if(head == NULL)
return 0;
ispalindrome(head->link, h1);
if(*h1)
{
if(head->data != (*h1)->data)
return;
(*h1) = (*h1)->link;
}
return;
}
couple of typos are there:
1. int k=1 is not required
2. if(head == NULL)
return; // not return 0;
if() condition is not required.
void ispalindrome(node *head, node**h1)
{
if(head == NULL)
return 0;
ispalindrome(head->link, h1);
if(head->data != (*h1)->data)
return;
(*h1) = (*h1)->link;
return;
}
If you unroll the recursion what's happening is the algo is creating a 'n' additional pointers by passing head->link.
so basically all the algo is doing is constructing an array of additional pointers to each element and is visiting them in the reverse order and simultaneously comparing by to element at 'h1' in the forward order.
i.e. using an additional space of O(n) {array of n pointers}
Also a small suggestion on the terminology, people usually refer to next element as "head->next" rather than "head->link"
thanks
@chennavarri: You are correct it will take O(n) space for pointers. If we can destroy the linked list then we can pass by reference so that it will not create copies for every recursive call.
int is_palindrome(node *n1) {
static node *n2 = start;
static node *n_end = NULL;
if (n2->next == n_end)
return 2;
else if (n1->next == n_end) {
n_end = n1;
if (n2->data == n1->data) {
n2 = n2->next;
return 1;
}
else
return 0;
}
else {
do {
rc = is_palindrome(n1->next);
n1 = n2;
} while (rc == 1);
return rc;
}
}
If rc == 2 then link list is palindrome.
NOTE: I am learning efficient programming(i.e.. time & space optimized code,easily understandable code).If you find any error in my below code, could you please let me know errors/suggestions in the code.
struct list
{
int data;
struct list *next;
};
int isPalindromeRecursive(struct list *header, struct list **traverseNode)
{
if( (*traverseNode)->next == NULL )
{
*traverseNode = header->next;
return 1;
}
else if((*traverseNode)->next->next == NULL)
{
*traverseNode = header->next->next;
return header->data == header->next->data; // when list contains even no. of nodes
}
else
{
*traverseNode = (*traverseNode)->next->next;
if(!isPalindromeRecursive(header->next, traverseNode))
return 0;
if(header->data != (*traverseNode)->data)
{
return 0;
}
else
{
*traverseNode = (*traverseNode)->next;
return 1;
}
}
}
int isPalindrome(struct list *header)
{
if( header == NULL )
{
printf("\n Invalid list \n");
return -1;
}
else if(header->next == NULL)
{
return 1;
}
else if( header->next->next == NULL )
{
return header->data == header->next->data;
}
else
{
struct list *traverseNode = header;
if(isPalindromeRecursive(header, &traverseNode))
{
printf("\n list is Palindrome \n");
return 1;
}
else
{
printf("\n list is not Palindrome \n");
return 0;
}
}
}
- Anonymous February 08, 2011Using recursion we can check linked list is palindrome. #include "stdafx.h" #include <iostream> using namespace std; int ispalindrome(node*, int[], int&, int, int&); struct node { int data; struct node *link; }; int _tmain(int argc, _TCHAR* argv[]) { struct node *head=NULL, *ss=NULL; insert(&head, 1); insert(&head, 2); insert(&head, 3); insert(&head, 3); insert(&head, 2); insert(&head, 3); insert(&head, 1); int a[100]; int k=0, l=1; cout << "Is palindrome: " << ispalindrome(head1, a, k, 0, l) << endl; } int ispalindrome(node *head, int a[], int &i, int n, int &flag) { if(head == NULL) return 0; a[n++] = head->data; ispalindrome(head->link, a, i, n, flag); if(a[i++] != head->data) flag = 0; return flag; }