Amazon Interview Question
Software Engineer / Developersbool helpFunction(Node **head , Node *tail)
{
Node *t = tail;
if(t==null)
{
return true;
}
if(helpFunction(head , t->next))
{
Node * h = *head;
if(h->Data == t->Data)
{
(*head) = (*head)->next;
return true;
}
}
return false;
}
bool IsPalidrome(Node * head)
{
Node * head1 = head;
Node * tail = head->next;
return helpFunction(&head,tail);
}
Hi, I think, it always prints "Linked list is Palindrome". This is because,
1). we return either '-1' or '1' from 'compareLists'.
2). The return value is assigned to 'res' which in turn returned to the 'main' function.
3). The condition 'if(isPalindrome(head))' is always true for any input.
Returning '0' may solve the problem.
Regards,
Hari.
Node IsPallin(Node current, Node head)
{
if( head == null) return null;
if(current->next != null) {
head = IsPallin(current->next, head)
}
if(current->info != head->info) return null;
return head->next ?? head;
}
One can further optimize by adding a parameter to track the comparison and make it halved.
O(n) approach: a bit messy though
#1. Find the length of the list.
#2. Assuming the size is even, keep putting/pushing all the elements from the beginning till the mid to a stack[mimic a stack using an array]. Reverse the stack. If you are using array then you just have to traverse it in the reverse order, thats it.
#3. Now Pop out one element and compare that with NexttoMid element in the list. Keep doing this in a loop till,
# you reach end, in that case its indeed a palindrome.
# you find a mismatch, bail out, declaring that the list is not a palindrome.
# Done !
Space=O(n/2)= O(n)
Time=O(n)
Reverse the first half of the list in O(n).
Verify for palindrome.
Reverse the first half again.
Got the same question in Yahoo!
A simpler linear solution is as follows:
Node* pTempHead = head;
while (head != NULL)
{
if(head->next != NULL && head->next->next-> != NULL)
{
if (head->value == head->next->next->value)
{
pBeginPoint = head;
pTrailingEnd = head->next->next;
break;
}
head = head->next;
}
}
head = pBegnPoint;
if (pTrailingEnd != NULL)
{
while (head != pBeginPoint)
{
if (pTrailingEnd->Next != NULL)
{
if (head->value == pTrailingEnd->next->value)
{
pTrailingEnd = pTrailingEnd->Next;
head = head->Next;
}
}
}
}
Need to check for error logic and all ...
Algorithm:
- In LL, find the pivotal point in the LL, where one before and one after the pivotal point are equal
- Then start from the head of the LL until one before pivotal point, and one after the pivotal point and make sure the nodes are equal
- This is more efficient than recrusion or reversing LL
singly linke list palindrome...no big deal..just use recursion
first find the middle of the list..using one fast and slow iterators..
then traverse second half of the list in reverse order while first half in forward..
compare values
use a global variable flag to save the value of comparison.
but once the its no longer palindrome..we can't break the recursive calls..
so glabal variable flagchanged is used to keep track of the flag var.
int flag =0;
int changedflag =0;
node* reverse(node * n1,node* n2)
{
if(n1==NULL)
return n2;
else
{ node *temp = reverse(n1->next,n2);
if(temp->data == n1->data)
{
if(changedflag==0)
flag=1;
}
else
{
if(changedflag==0)
{ flag=0;
changedflag=1;
}
}
return n2->next;
}
}
sorry!! indentation went wrong due to copy pasting from editor
int flag =0;
int changedflag =0;
node* reverse(node * n1,node* n2)
{
if(n1==NULL)
return n2;
else
{ node *temp = reverse(n1->next,n2);
if(temp->data == n1->data)
{
if(changedflag==0)
flag=1;
}
else
{
if(changedflag==0)
{ flag=0;
changedflag=1;
}
}
return n2->next;
}
}
How about this:
If extra O(n) space is allowed then. Use 1 stack and 1 queue.
put first half in queue. Second half in stack.
Then pop from stack and dequeue from list and compare.
If length if list is even both will be empty in the end.
Else the middle element will remain, in the stack or queue (your choice).
best wud be to take two pointers...fast and slow.....find the middle point. now take a third global pointer point it to head...use recursion(NO NEED TO REVERSE THE LIST)
node * global_head;//points to original head
int main()
{
node *head, *fp,*sp;//given head, fastpointer, slowpointer
fp=sp=global_head=head;
if(head==NULL || head->next==NULL||(head->next->next==NULL&&head->val==head->next->val))
{
cout<<"yes palindrome";
exit(0);
}
while(fp==NULL||fp->next==NULL)
{
fp=fp->next->next; sp=sp->next;
}
check(sp->next);
return 0;
}
void check(node *p)
{
if (p==NULL) return;
check(p->next);
if(global_head->val!=p->head)
{
cout<<"NOT A PALINDROME";
exit(0);
}
global_head=global_head->next;
}
/* Program to check if a linked list is palindrome */
#include<stdio.h>
#include<stdlib.h>
#define bool int
/* Link list node */
struct node
{
char data;
struct node* next;
};
void reverse(struct node**);
bool compareLists(struct node*, struct node *);
/* Function to check if given linked list is
palindrome or not */
bool isPalindrome(struct node *head)
{
struct node *slow_ptr = head;
struct node *fast_ptr = head;
struct node *second_half;
struct node *prev_of_slow_ptr = head;
char res;
if(head!=NULL)
{
/* Get the middle of the list. Move slow_ptr by 1
and fast_ptrr by 2, slow_ptr will have the |_n/2_|th
node */
while((fast_ptr->next)!=NULL &&
(fast_ptr->next->next)!=NULL)
{
fast_ptr = fast_ptr->next->next;
/*We need previous of the slow_ptr for
linked lists with odd elements */
prev_of_slow_ptr = slow_ptr;
slow_ptr = slow_ptr->next;
}
/* Case where we have even no of elements */
if(fast_ptr->next != NULL)
{
second_half = slow_ptr->next;
reverse(&second_half);
slow_ptr->next = NULL;
res = compareLists(head, second_half);
/*construct the original list back*/
reverse(&second_half);
slow_ptr->next = second_half;
}
/* Case where we have odd no. of elements. Neither first
nor second list should have the middle element */
else
{
second_half = slow_ptr->next;
prev_of_slow_ptr->next = NULL;
reverse(&second_half);
res = compareLists(head, second_half);
/*construct the original list back*/
reverse(&second_half);
prev_of_slow_ptr->next = slow_ptr;
slow_ptr->next = second_half;
}
return res;
}
}
/* Function to reverse the linked list Note that this
function may change the head */
void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
*head_ref = prev;
}
/* Function to check if two input lists have same data*/
int compareLists(struct node* head1, struct node *head2)
{
struct node* temp1 = head1;
struct node* temp2 = head2;
while(temp1 && temp2)
{
if(temp1->data == temp2->data)
{
temp1 = temp1->next;
temp2 = temp2->next;
}
else return 0;
}
/* Both are empty reurn 1*/
if(temp1 == NULL && temp2 == NULL)
return 1;
/* Will reach here when one is NULL
and other is not */
return 0;
}
/* Push a node to linked list. Note that this function
changes the head */
void push(struct node** head_ref, char new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to pochar to the new node */
(*head_ref) = new_node;
}
/* Drier program to test above function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
push(&head, 'p');
push(&head, 'e');
push(&head, 'e');
push(&head, 'p');
/* p->e->e->p */
if(isPalindrome(head) == 1)
printf("Linked list is Palindrome");
else
printf("Linked list is not Palindrome");
getchar();
return 0;
}
Copied from Geeksforgeeks
Here is the solution.
Algorithm:
1. Get the middle of the linked list.
2. Reverse the second half of the linked list.
3. Compare the first half and second half.
4. Construct the original linked list by reversing the
second half again and attaching it back to the first half
Implementation:
Time Complexity O(n)
- Initrd March 07, 2010Space Complexity O(1)