Amazon Interview Question SDE-2s
Country: India
Interview Type: Written Test
if the LL is read only - there is another way.
1. traverse list form start to middle and put the data to a stack.
2. from middle to end, pop the data from stack and compare to the current node.
Note: needs to take care about even and odd size list.
This will take O(n) space.
Reversing the list is not required.
1. use two pointers (one with normal speed, one with double speed), to get 'middle' and 'last' nodes of the list.
2. now you have start,middle,last pointers.
->do the following until you start is the middle one.
a. starting from 'middle' , track the previous of the last node (say prevLast).
b. compare start and last node's data
if they are not same, then not a palindrome.
if they are same, advance start and make prevLast as last.
->reached till middle ??, then its palindrome :)
**tweak required for even sized list. but logic is same.
Also, if followed the reverse logic, the starting node will point at end node of original linked list and the traverse will happen in backward direction, i.e, now starting pointer of reversed list and starting pointer of original list will be incremented and corresponding values increased.
Reach to the middle element and reverse the linked list from the mid to the last element. Now compare the first half and second half (which was reversed earlier). If at any point the two elements don't match return false. Else return true. I have not considered the case for odd and even distinctly. A little modification might do.
package oracle.prakash.investmentbank.test;
public class SinglePalinList<T extends Comparable> {
public SinglePalinList() {
super();
}
private T data;
private SinglePalinList<T> next;
private SinglePalinList<T> head;
private SinglePalinList<T> tail;
public static void main(String[] args) {
SinglePalinList<Integer> singlePalinList = new SinglePalinList<Integer>();
int[] a={10,20,30,20,10};
for(int i:a) {
singlePalinList.insert(i);
}
singlePalinList.traverse(singlePalinList.getHead());
System.out.println("--------------------------------------------");
System.out.println(singlePalinList.palin(singlePalinList.getHead()));
}
public boolean palin( SinglePalinList<T> head) {
if(head==null) return false;
SinglePalinList<T> head1 = head;
SinglePalinList<T> mid = head1.getNext()!=null?head1.getNext().getNext():head1.getNext();
while(mid!=null) {
head1 = head1.getNext();
mid = mid.getNext()!=null?mid.getNext().getNext():mid.getNext();
}
SinglePalinList<T> prev = null;
SinglePalinList<T> temp = null;
prev = head1;
mid = prev;
head1 = head1.getNext();
while(head1!=null) {
temp = head1;
head1 = head1.getNext();
temp.setNext(prev);
prev = temp;
}
mid.setNext(null);
while(head!=null && prev!=null) {
if(!head.getData().equals(prev.getData())) {
return false;
}
head = head.getNext();
prev = prev.getNext();
}
return true;
}
public void reverse(SinglePalinList<T> head1) {
}
public void insert(T data) {
SinglePalinList<T> head = this.getHead();
SinglePalinList<T> item = new SinglePalinList<T>(data);
if(head==null) {
this.setHead(item);
this.setTail(item);
}
else {
this.getTail().setNext(item);
this.setTail(item);
}
}
public void traverse(SinglePalinList<T> head) {
while(head!=null) {
System.out.println(head.getData());
head = head.getNext();
}
}
public SinglePalinList(T data) {
this.setData(data);
}
public void setData(T data) {
this.data = data;
}
public T getData() {
return data;
}
public void setNext(SinglePalinList<T> next) {
this.next = next;
}
public SinglePalinList<T> getNext() {
return next;
}
public void setHead(SinglePalinList<T> head) {
this.head = head;
}
public SinglePalinList<T> getHead() {
return head;
}
public void setTail(SinglePalinList<T> tail) {
this.tail = tail;
}
public SinglePalinList<T> getTail() {
return tail;
}
}
#include<stdio.h>
#include<conio.h>
#include<iostream>
struct Node
{
int data;
Node *next;
};
void reverse_linklist(Node **root)
{
if((*root)->next == NULL)
{
return;
}
Node *first = NULL;
Node *second = NULL;
first = *root;
second = first->next;
reverse_linklist(&second);
first->next->next = first;
first->next = NULL;
*root = second;
}
void Insert_linklist(Node **root, int num)
{
if(*root == NULL)
{
*root = new Node();
(*root)->data = num;
(*root)->next = NULL;
return;
}
else
{
Node *temp = *root;
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next = new Node();
temp = temp->next;
temp->data = num;
temp->next = NULL;
return;
}
}
void Print(Node *t)
{
while(t != NULL)
{
printf("%d\n",t->data);
t = t->next;
}
}
Node *mid_linklist(Node *root)
{
//If Even Node of Nodes 1 2 3 4 we should return address of 3
//If Odd No of nodes then we should return 1 2 3 4 5 index of 4
Node *p1 = root;
Node *p2 = root;
while(p2 && p2->next)
{
p1 = p1->next;
p2 = p2->next;
p2 = p2->next;
}
return p1;
}
bool Compare_linklist(Node *p, Node *q)
{
while(p && q)
{
if(p->data != q->data)
{
return false;
}
p = p->next;
q = q->next;
}
return true;
}
bool CheckPalindrome(Node *head)
{
bool flag = false;
Node *mid = mid_linklist(head);
reverse_linklist(&mid);
flag = Compare_linklist(head,mid);
reverse_linklist(&mid);
return flag;
}
int main()
{
Node *head = NULL;
Insert_linklist(&head,1);
Insert_linklist(&head,2);
Insert_linklist(&head,3);
Insert_linklist(&head,3);
Insert_linklist(&head,2);
Insert_linklist(&head,1);
bool flag = CheckPalindrome(head);
if(flag)
{
printf("PalinDrome List\n\n");
}
Print(head);
getch();
}
The function requires the number of nodes in the singly linked list.
int linklist_is_palindrome (singly_node_t *head, int n, singly_node_t **end)
{
if (n == 1) {
*end = head;
return (1);
}
if (n == 2) {
*end = head->next;
return (head->value == (*end)->value);
}
singly_node_t *last;
if (!linklist_is_palindrome(head->next, n-2, &last)) {
return (0);
}
*end = last->next;
return (head->value == (*end)->value);
}
I had same idea to use recursion form the middle instead of reversing LL, but I think there are couple of bugs here.
last is actually mid
*end = last->next; should be *end = (*end)->next;
Also I would return 'end' if current call is successful and null if not. This avoid double pointer and parameter modification.
Use recursion
bool CheckSingleLinkedListIsPalindromeOrNotRecursion(linkedListNode *ptr,linkedListNode **begin){
if(ptr == NULL){
return true;
}
if(ptr->next == NULL){
//Reached last node
if(ptr->value == (*begin)->value){
*begin = (*begin)->next;
return true;
}
return false;
}
bool truthValue = CheckSingleLinkedListIsPalindromeOrNot(ptr->next,begin);
if(!truthValue){
return false;
}
return ptr->value == (*begin)->value?(*begin)=(*begin)->next,true:false;
}
Creating the reverse won't work as space will not be constant...
My approach:
The first node needs n-1 to reach to its equivalent node in a palindrome....
the second node needs n-3 to its equivalent node
n so on...till n-x = 0 which is the middle node.....
time complexity = o(n^2)
Please correct me if I am missing something...
1. take 2 pointers which points to the beginning and middle element of LL
- Vin August 11, 20132. reverse the LL from middle to end of LL
3. now compare the values pointed by beginning and middle elements. is same increment both pointers. else not a palindrome(break)
4. continue step 3 until second pointer reaches the end
5. reverse the second half of the LL to restore the original LL.