## Expedia Amazon Interview Question for Software Engineer / Developers

Country: United States

Comment hidden because of low score. Click to expand.
8
of 8 vote

1) Find the middle of the linked list using two pointers.
2) Reverse the linked list from the middle(second half).
3) Now two pointers, 1st one from start of list, 2nd one from middle of list.
Compare the list elements by moving pointers each time by one.
Check for palindrome property.

Comment hidden because of low score. Click to expand.
0

VillageMonkey,

I like that you have given also sol which is easy to understand logic.

now coming to your sol. we should not modify the data provided in question unless it is not explicitly given.

Comment hidden because of low score. Click to expand.
0

It's OK; he can re-reverse the part of the list that he reversed, restoring the list to its original state before exiting the function.

Comment hidden because of low score. Click to expand.
0

How to find the middle of the list, is it by first finding the length and then traversing the list by half of that number? Is there any better method? Pls help!

Comment hidden because of low score. Click to expand.
1
of 1 vote

middle of the list can be found by using two pointers. increment the first pointer by 1 node and 2nd pointer by 2 nodes. The first pointer will point to the middle when the 2nd pointer points to the last node.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
6
of 6 vote

1.find middle node(fast runner/slow runner method)
2.construct a stack of size n/2.
3.push elements till middle point is reached.
4.at n+1th element start popping and compare with list.
(handle suituation for even and odd number of elements)

Comment hidden because of low score. Click to expand.
0

What is fast runner/slow method?

Comment hidden because of low score. Click to expand.
0

@avenger its finding middle via using two pointers. Increment one pointer via 1 and another by 2.

Comment hidden because of low score. Click to expand.
4
of 4 vote

Use two pointer strategy - advance one pointer twice as fast as the other pointer. Say you advance pointer 'i' at half the speed of pointer 'j'

While pointer 'j' not at end of linked list:
1. Push everything encountered by pointer 'i' on to a stack.
2. Then advance pointer 'i' to the end, traversing each element once.
3. For each element encountered, check that it matches with element popped from stack.

The below code in C# handles both lists of even and odd sizes:

``````public bool IsPalindrome()
{
int count=1;
bool moveBoth=false;
Stack<Node> pal=new Stack<Node>();

pal.Push(i);

while(j.next!=null)
{
if(moveBoth)
{
i=i.next;
j=j.next;
moveBoth=false;
pal.Push(i);
}
else
{
j=j.next;
moveBoth=true;
}
count++;
}

if (count % 2 ==0 && i != null)
{
pal.Push(i.next);
}
while(i!=null)
{
if(pal.Count<1) return false;
if(i.data.CompareTo(pal.Pop().data)!=0)
return false;
i = i.next;
}

return true;
}``````

Comment hidden because of low score. Click to expand.
0

Excellent!!

Comment hidden because of low score. Click to expand.
0

Can you please tell me what the complexity is? both the time and space complexity

Comment hidden because of low score. Click to expand.
0

excellent indeed!!

Comment hidden because of low score. Click to expand.
0

very nice approach

Comment hidden because of low score. Click to expand.
0

is the following code true for comparison of the popped value and the value in the second half of palindrome ? please someone take a look -

while(true)
{
if (i->data == i->next->data && i->data == pop())
i = i->next->next;
return true;
else if (i->data == pop())
return true;
else
return false;
}

Comment hidden because of low score. Click to expand.
0

Is solution Irrespective of Odd and Even length of the Link list??

Comment hidden because of low score. Click to expand.
0

I think you need to accomodate for the odd & even cases differently. I tried implementing this, and would stop inserting into the stack as soon as the faster pointer is null (even) or that its "next" is null (odd). In the even case, since the slow pointer is already pointing past the mid-point, I would need to immediately check it against the top element of the stack. Details might vary based on your implementation though but the idea works.

Having said that, I think this solution is good since it's only 1-pass. But if we are allowed to use so much memory then I might as well traverse the whole list to create a string then work off the string instead.

Comment hidden because of low score. Click to expand.
3
of 3 vote

Method-1: Use Recursion

You need to compare the first and last node in the first loop and then compress the list

{
}

bool isPalindromeRec(Node **l, Node *r)
{
if (!r) // terminating condition
return true;

// If the sublist is not palindrome then don't need to check further
return false;

bool flag = (r->data == (*l)->data);

*l = (*l)->link; // Move l forward

return flag;
}

Method-2: Use reverse method

Move to the middle of the list.
Reverse the second half
compare the first and reversed second half one node at a time, if the are same return true else false.
Reverse the 2nd half again to get the original list.

Time Complexity: O(n)
Extra Space used: O(1)

Comment hidden because of low score. Click to expand.
0

Nice recursive solution!

Comment hidden because of low score. Click to expand.
2
of 2 vote

This can be optimized using a doubly linked list.

1. Traverse from head and tail at the same time from node to node and check if value is the same. (head ++ and tail --)
2. continue as long as head == tail or head > tail pointer.
3. If there was no change observed in the values as head and tail in each jump then its a palindrome, else its not.

Comment hidden because of low score. Click to expand.
0

what will be the time complexity of this approach??

Comment hidden because of low score. Click to expand.
0

O(LogN)

Comment hidden because of low score. Click to expand.
0

its O(n/2)~ O(n)

Comment hidden because of low score. Click to expand.
0

They have not mentioned the doubly linked list, so can we use it? I don't have idea...

Comment hidden because of low score. Click to expand.
0

but here i think we cannot observe the condition of head>tail as it is a heap allocated memory.

Comment hidden because of low score. Click to expand.
0

@NP there is no need of the condition head>tail.. head==tail would be sufficient . cause at some time both will be equal. use while loop.
e.g.

``````while(head!=tail && .......){
---------
---------
tail=tail->back;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

reverse the linked list and compare with the original..O(n)

Comment hidden because of low score. Click to expand.
0

private Node tail;

// Reversing nodes in a list
void reverse(){
Node temp = null;

return;
}

if(tail == null){
return;
}

while(current != null) {
Node loopNode = current.next;
current.next = temp;
temp = current;
current = loopNode;
}
}

private static class Node{
int element;
Node next;

public Node(int element){
this.element = element;
}
}

Comment hidden because of low score. Click to expand.
0

This is better solution compared to finding center of linkedlist.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Find the length of the list, and call the recursive function below.

``````Node * isPali(Node * head, int length){
if(length == 1){
}
if(length == 2){
}else{
return null;
}
}
if(p == null){
return null;
}
return p->next;
}else{
return null;
}
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

The below code uses two pointer strategy and checks for Palindrome Lists. It is also using C++ template mechanism to make it more general.

``````bool checkPalindrom()
{
return false;
return true;

stack<T> st;
st.push(q->data);
bool turn = false;
int size = 1;
while(p)
{
if(turn)
{
q = q->next;
st.push(q->data);
turn = false;
}
else
{
turn = true;
}
p = p->next;
size++;
}
q = q->next;
if(size%2 != 0)
{
st.pop();
}
while(q)
{
if(st.top()==q->data)
{
q = q->next;
st.pop();
}
else
{
return false;
}
}
return true;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Use stack (recursive function or explicitly)

Comment hidden because of low score. Click to expand.
0
of 0 vote

/*
METHOD 1 (By reversing the list)

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
*/

/* Program to check if a linked list is palindrome */
#include<stdio.h>
#include<stdlib.h>
#define bool int

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 */
{
struct node *second_half;
char res;

{
/* 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;

/*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);

/*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 */
{
struct node* prev = NULL;
struct node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
}

/* Function to check if two input lists have same data*/
{

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
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 */

/* move the head to pochar to the new node */
}

/* Drier program to test above function*/
int main()
{

/* p->e->e->p */
else

return 0;
}
//Time Complexity O(n)
//Space Complexity: O(1)

Comment hidden because of low score. Click to expand.
0
of 0 vote

use two pointers and a stack/array. One fast pointer moving two nodes a time and one slow pointer moving one node a time. Moving the two pointers at the same time. Before the faster pointer reaches the end, push the node pointed by the slow pointer to the stack. After the faster pointer reaches the end, pop the stack and compare it with the node pointed by the slow pointer. Only one time link list traversal is needed.

Comment hidden because of low score. Click to expand.
0

Well you are traversing linked list twice, not once!!
Both faster and slower pointers are traversing linked list. The fact that they are doing it at the same time does not change anything (it is not parallel).

This approach is exactly like the following:

we traverse the list once and find out the number of the elements. Then we traverse the list again and push them into a stack until we get to the middle of the list, then we pop them from middle to the end.
here also we are traversing the list twice.

Comment hidden because of low score. Click to expand.
0

Nice solution guys

Comment hidden because of low score. Click to expand.
0
of 0 vote

while(1)
{

while(q!=NULL && q->next!=NULL )
{
r=q;
q=q->next;
}

if(p==q || p== NULL || q==NULL)
{
printf("palindrome\n");
break;

}

if(p->value != q->value)
{

printf("Not a palindrome\n");
break;
}

r->next=NULL;

}

Comment hidden because of low score. Click to expand.
0

Inefficient!

Comment hidden because of low score. Click to expand.
0

Not just inefficient, its WRONG

Comment hidden because of low score. Click to expand.
0
of 0 vote

thanks Anonymous, liked the approach.. :)

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````#include <stdio.h>

struct lnode {
void *data;
struct lnode *next;
};

struct lnode *newNode(void *data) {
struct lnode *node = (struct lnode *) malloc(sizeof(struct lnode));
node->data = (char *) malloc(sizeof(strlen((char *)data)+1));
node->next = NULL;
strcpy((char *)node->data, (char *)data);
return node;
}

typedef struct {
struct lnode *top;
} Stack;

Stack *newStack() {
Stack *s = (Stack *) malloc(sizeof(Stack));
s->top = NULL;
return s;
}

void *pop(Stack *s) {
struct lnode *node;
void *data;

if(s->top==NULL)
return NULL;

node = s->top;
s->top = node->next;
data = node->data;
free(node);
return data;
}

void push(Stack *s, void *data) {
struct lnode *node = newNode(data);
node->next = s->top;
s->top = node;
}

int isPalindrome(struct lnode *ll) {
struct lnode *l2, *current;
Stack *s = newStack();

current = ll;
while(current) {
push(s, current);
current = current->next;
}

current = l2 = pop(s);
while(current) {
current->next = pop(s);
current = current->next;
}

while(ll!=NULL && l2!=NULL && strcmp((const char *)ll->data, (const char *)l2->data)==0) {
ll = ll->next;
l2 = l2->next;
}
return ll==NULL && l2==NULL;
}

int main() {
struct lnode *current, *ll = NULL;
char *words[] = {"M", "A", "L", "A", "Y", "A", "L", "A", "M"};
int i;

ll = current = newNode(words);
for(i=1; i<9; i++) {
current->next = newNode(words[i]);
current = current->next;
}

printf("String %s Palindrome\n", (isPalindrome(ll)) ? "Is" : "Is not");

return 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

@2 pointers' anonymous .. gud approach !

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def test_symmetric (head):

def helper(curr, node):
if not curr: return node
if curr == helper(curr.next, node)
return node.next``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

mark=0;
while(ptr1!=NULL&&ptr2!=NULL)
{
push(ptr1->data);//push to stack
ptr1=ptr1->next;//move the pointer to one step
ptr2=ptr2->next;//move ptr2 to 2 steps
if(ptr2!=NULL)
ptr2=ptr2->next
else mark=1;//if length of linked list is odd
}
if(mark==1)//means odd length
pop();
ptr1=ptr1->next
while(!stack_empty()&&ptr1!=NULL)
{
compare(top_stack(),ptr1->data);
if(both r same)
pop();
else return GIVEN LL is NOT PALINDROME
}
if(stackis_empty())GIVEN LL is PALINDROME
else GIVEN LL is NOT PALINDROME

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can't you just read the value of each linked list node into a string as you traverse? Then make a new string equal to the reverse of the original string (this is a string function) and compare. If a character is not the same, return false. This runs in O(n) + O(n) = O(n) time.

Comment hidden because of low score. Click to expand.
0
of 0 vote

we can do this by recursive call. fast pointer will be moving till the end of the list recursively and wen it reaches end thats when we start comparing the fast->data with the slow->data(where slow is in the beginning). we move slow pointer before recursive call is returned.

Comment hidden because of low score. Click to expand.
0
of 0 vote

use 2 pointers fast and slow. when traversing slow should reverse the pointers. when fast reaches end slow reaches middle of list and all nodes before slow are reversed. now just compare reverse list with slow pointer

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class LinkPalin {

class MyBool {
public boolean val;

public MyBool() {
}
}

class Node {
public char ch;
public Node next;

public Node(char ch) {
this.ch = ch;
}

@Override
public String toString() {
return String.valueOf(ch);
}
}

int n = 0;

n++;
}

public boolean isPalin() {
MyBool b = new MyBool();
b.val = true;
return b.val;
}

public Node palin(Node l, MyBool b, int depth) {
Node r = l.next;
if (depth > 1)
r = palin(r, b, depth - 1);
else if (depth == 1 && n % 2 == 1)
r = r.next;

b.val &= l.ch == r.ch;
return r.next;
}

public void print() {
System.out.print(n);
System.out.print(": ");

while (cur != null) {
System.out.print(cur.ch);
System.out.print(' ');
cur = cur.next;
}
System.out.println();
}

public void test(MyBool b) {
b.val = false;
}

public static void main(String[] args) {

p.print();
System.out.print(p.isPalin());
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

I have used Recursion to solve this prob:
here back pointer will start from last node and temp will start fetching nodes from start.

Please go through the code, You can also exe it... its working...!

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct nodetype
{
int info;
struct nodetype *next;
};
typedef struct nodetype *node;

node createNode()
{
node n;
n=(node)malloc(sizeof(struct nodetype));
return n;
}

{
printf("1");
printf("2");

{
printf("3");
printf("4");
printf("5");
printf("6");
printf("7");

}

else
{
while(temp->next!=NULL)
{
temp=temp->next;
}

}
}

{
node temp;
{
printf("List is empty\n");
}
else
{

while(temp!=NULL)

{

printf("\nElement : %d",temp->info);
temp=temp->next;
}
}
}

node checkPalindrome(struct nodetype **head,struct nodetype *back)
{
node temp;
if(back->next!=NULL)
{
back=back->next;
}
if(back->next==NULL)
{
}
if(back->info!=temp->info)
{

printf("\n not \n");
return temp;
}
temp=temp->next;
return temp;
}

int main()
{
int ch,item;

struct nodetype *list=NULL;

do
{
printf("2:show the List \n");
printf("3:check Palindrome \n");
printf("0:Exit from Program \n");
scanf("%d",&ch);
switch(ch)

{
case 1:
{
printf("\nEnter the item to add in List: ");
scanf("%d",&item);
break;
}
case 2:
{
printf("Element in List are :\n");
showList(&list);
break;

}
case 3:
{
node res;
printf("\n The List is");
res=checkPalindrome(&list,list);
printf("Palindrome \n");
break;
}
case 0:
{
printf("\n Thanks for using this software");
break;
}
}

}while(ch!=0);

getch();
return 0;
}

I have an Issue on this:
how to stop and step out from recursion when required condition is met....?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Have a stack and a queue
Traverse the linked list and add every node to stack and to queue
Now, till the stack is empty,
check pop()==dequeue()
if there is a mismatch, say it is not a palindrome
if stack gets empty, then it is a palindrome

Here is a sample code.. I have assumed this with a String. Just we have to traverse the linked list instead of String in this code

``````import java.util.*;
class palin
{
public static void main(String []args)
{
Stack s=new Stack();
for(int i=0;i<str.length();++i)
{
s.push(str.charAt(i));
}
while(!s.isEmpty())
{
if(s.pop()!=q.remove())
{
System.out.println("Not a palindrome");
System.exit(1);
}
}
System.out.println("palindrome");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why not take this simple approach:

Step 1: Push the entire list in stack using a pointer ptr1.
Step 2: Take another pointer ptr2 and start iterating this pointer 1 step at a time to front.
Step 3: Start popping off the stack at the same time and compare the values (popped out value with the pointer's data)
Step 4: If this Linked List is a palindrome then these values should always match.

Comment hidden because of low score. Click to expand.
0

Your solution will work but can be improved by only pushing first half of elements on stack. Middle of linkedlist can be found using slow and fast runner approach. Once we reach at the middle we start comparing element pointed by slow pointer and popping element on top of stack.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int isPal(node *tmp)
{
static int result =2;

if(tmp->next) {
result = isPal(tmp->next);
if(!result) return 0;
if(result==1) return 1;
}

return result;
}
else return 0;
}``````

Comment hidden because of low score. Click to expand.
0

Algo :

Recursively, move to end of list.. Once you do, compare end with head..if equal, move head forward and unwind the stack to compare, head(moved forward by n places) and element at (last -n)th position.

Comment hidden because of low score. Click to expand.
0
of 0 vote

just simply reverse the linked list ,it can be done in O(n) time.
then compare each node which is also O(n) time.
on the whole it takes O(2n),which is O(n) any way.

Comment hidden because of low score. Click to expand.
0
of 0 vote

int checkpalindrome(struct node *root, struct node **left)
{
int ret;

if(root != NULL)
{
ret = checkpalindrome(root -> next, left);
if(root -> data != (*left) -> data)
return 0;
(*left) = (*left) -> next;
return ret;
}

return 1;
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

int checkpalindrome(struct node *root, struct node **left)
{
int ret;

if(root != NULL)
{
ret = checkpalindrome(root -> next, left);
if(root -> data != (*left) -> data)
return 0;
(*left) = (*left) -> next;
return ret;
}

return 1;
}

Comment hidden because of low score. Click to expand.
0

Really nice:)

Comment hidden because of low score. Click to expand.
0

nice approach..
I believe the left argument here is the address of the original list.

Comment hidden because of low score. Click to expand.
0
of 0 vote

public boolean checkPalindrome(Node n)
{
char[] array = null;
int index = 0 ;

while(n.next != null)
{
array[index] = n.val;
index++;
n = n.next;
}

int i = 0 ;
int j = array.length - 1;

int lengthofArray = 0 ;

while (i<=j)
{
if(array[i] ! = array[j])
return false;
else
{
if(arrayLength%2 != 0)
{
if(i == j-2)
return true;
else
{
i++;
j--;
}

else
{
if( i == j -1 )
{
return true;
}
else
{
i++;
j--;
}
}
return false;
}

}

Here is how above code works
1. Build character array from linked list.
2. Start two pointers , one from the very first element of character array and other from end of the array.
3. Keep comparing corresponding elements.
4. return true if all the corresponding elements are equal , else return false.

Comment hidden because of low score. Click to expand.
0

this is not very elegant solution, since u are using extra space, and u are specifically asked to check the palindrome in a link list

Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Take two pointers, run second pointer twice as fast as first pointer.
2) when the fast pointer reaches the end of the list , the first pointer reaches the middle
3) calculate the sums of ascii values from start to mid and mid+ 1 to end
4) compare the two sums. if its same, that means its a palindrome.

Here is the code

int ispallindrome(LIST * node)
{
LIST *first,*second;
first = node;
second =node;
while (second !=NULL){
first=first->next;
second=second->next->next;
}

//first pointer will point to the middle of the list
LIST *trav;
int sum=0,sum1=0;
trav =node;
while (trav!=first){
sum += trav->value;
trav = trav->next;
}
//calculate the sum from mid+1 position till the end
trav = first->next;
while( trav!=NULL){
sum1 +=trav->value;
trav=trav->next;
}

if ( sum1 = sum)
return 1;
else
return 0;

}

this algo takes O(n)time

Comment hidden because of low score. Click to expand.
1
of 1 vote

while (second !=NULL){
first=first->next;
second=second->next->next;
}

This will cause a segmentation fault, when number of elements in the list are odd. Consider a list only 1 elements and the above code will result in segmentation fault, because the code second->next->next will result in NULL->next.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static boolean listPalindromeCheck(LinkedList<Character> list)
{
int sz = list.size()/2;
char[] arr1=new char[sz];
ListIterator<Character> itr=list.listIterator();
int i=0;
for (i=0;i<sz;++i)
arr1[i]=itr.next();
if(list.size()%2>0)
itr.next();
for(--i;i>=0;--i)
{
if(arr1[i] != itr.next().charValue())
return false;
}
return true;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

1. Treat Linked List a Stack Data Type.

``````foreach character in string
if( the top of the stack is same as the present character)
pop from stack
else
push character into stack

if stack isempty
palindrome
else
not palindrome``````

Comment hidden because of low score. Click to expand.
0

This doesn't work because if input is MADAM,
you will never pop.
Or in the case of MADDDDAM, you will pop at the wrong character.

You need to use the size of the list to know when to pop.

Comment hidden because of low score. Click to expand.
0

Correct !!
Another way i can think of is,

to have a stack and a Queue of linked list.

``````create a stack and a Queue of linked list.

insert each character both into the stack and the queue.
have count of length

now for half the length match each character from both Q  to corresponding stack  character
(pop from stack and get from stack and get front from Q)
if it does not match at any point
return false

return true;``````

space complexty 2O(n) ~ O(n)
Time Complexity O(n)

Comment hidden because of low score. Click to expand.
0

Then it's better we just use one stack and then pushing till half the string further comparing each character from the pop element of the stack. This will take less space.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I have used Recursion to solve this prob:
here back pointer will start from last node and temp will start fetching nodes from start.

Please go through the code, You can also exe it... its working...!

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct nodetype
{
int info;
struct nodetype *next;
};
typedef struct nodetype *node;

node createNode()
{
node n;
n=(node)malloc(sizeof(struct nodetype));
return n;
}

{
printf("1");
printf("2");

{
printf("3");
printf("4");
printf("5");
printf("6");
printf("7");

}

else
{
while(temp->next!=NULL)
{
temp=temp->next;
}

}
}

{
node temp;
{
printf("List is empty\n");
}
else
{

while(temp!=NULL)

{

printf("\nElement : %d",temp->info);
temp=temp->next;
}
}
}

node checkPalindrome(struct nodetype **head,struct nodetype *back)
{
node temp;
if(back->next!=NULL)
{
back=back->next;
}
if(back->next==NULL)
{
}
if(back->info!=temp->info)
{

printf("\n not \n");
return temp;
}
temp=temp->next;
return temp;
}

int main()
{
int ch,item;

struct nodetype *list=NULL;

do
{
printf("2:show the List \n");
printf("3:check Palindrome \n");
printf("0:Exit from Program \n");
scanf("%d",&ch);
switch(ch)

{
case 1:
{
printf("\nEnter the item to add in List: ");
scanf("%d",&item);
break;
}
case 2:
{
printf("Element in List are :\n");
showList(&list);
break;

}
case 3:
{
node res;
printf("\n The List is");
res=checkPalindrome(&list,list);
printf("Palindrome \n");
break;
}
case 0:
{
printf("\n Thanks for using this software");
break;
}
}

}while(ch!=0);

getch();
return 0;
}

Comment hidden because of low score. Click to expand.
0

I dont understand. Are you creating another list which is reverse of the initial list? If so what if the string length is 1 million?

Comment hidden because of low score. Click to expand.
1
of 1 vote

Very good solution. Was thinking of sometime along the line u have solved. The only limitation will be stack size used for recursion.

Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Use the slow runner/fast runner technique. and use all the values slow runner is running through and add it to a stack. Also keep a counter to count the number of elements (Use the Fast runner to keep the count).
2)Follow this step only if the total count of the string is odd, else procedd to next step. Pop the first element in the stack.
3) Now use the slow runner and proceed one node to another. Compare the node's value with the last element popped. if they are same then proceed, else break.

Comment hidden because of low score. Click to expand.
0
of 0 vote

return 1;
}
else
{
int isp;
isp = helperPalindrome(&left,right);
return isp;
}
}

int helperPalindrome(struct node **left, struct node *right){
int hisp;
if(right == NULL){
return 1;
}
else
{
hisp = helperPalindrome(left,right->next);
if(hisp == 1){
if((*left)->data == right->data){
*left=(*left)->next;
return 1;
}
else
return 0;
}
return 0;
}
}
done in o(1) space and o(1) time

Comment hidden because of low score. Click to expand.
0
of 0 vote

What if we push the entire string into a stack and then pop it and see if the two strings are equal? What will be the time complexity of this approach?

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. create a char pointer
char *ptr;

2. traver the linked list and keep adding element to ptr to form a string

eg.
c->a->t->a->c
then do as
*ptr = c;
*(ptr+1) = a;
*(ptr+2)=t;
...
.
.
*(ptr+5)='\0'; // ofcourse this would be a for loop
//so *(ptr+i) till node!=NULL

3. then again traverse linked list from starting and compare element from end of string ..
eg.. compare 1st node with * (ptr+n-1) // (ptr+n) is '\0';
.. compare 2nd node with * (ptr+n-2)
.. compare 3rd node with * (ptr+n-3)

and so on...

time complexity O(n)
space complexity o(1);

Comment hidden because of low score. Click to expand.
0
of 0 vote

void pelindrome(node *h)
{
node *p;
int *stack=NULL;
int n=0,i;
for(p=h;p!=NULL;p=p->next)
{
stack=(int *)realloc(stack,sizeof(int));
*(stack+n)=p->data;
n++;
}
i=n/2;
for(p=h;i>=0;p=p->next,i--)
{
if(p->data != *(stack+i))
break;
}

if(i<n/2)
printf("it is not a pelindrome");
else
printf("it is a pelindorme");
for(i=0;i<25;i++)
printf("%d ",stack[i]);
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

/* Interview questions
*
* Author : touzzie
* mailto:tousifmt87@gmail.com
*/

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0

typedef struct node
{
char st;
}LIST_t;

typedef int BOOL;

LIST_t *pCur = NULL, *pPrev = NULL;

/*
* This function accepts multiword string from user
* and maintain it in a linked list.
*
* Implements linked list as QUEUE
*
* \param void
* \return void
*
*/

void createString(void)
{
char tmp;

printf("Enter the string(case sensitive) : ");
while((scanf("%c",&tmp)) && (tmp != '\n'))
{
pCur = (LIST_t *)malloc(sizeof(LIST_t));
pCur->st = tmp;

/* create first node */
{
pPrev = pCur;
}
else
{
pPrev = pCur;
}
}

}

#if 0
/*
* Display String
*
* \param void
* \return void
*
*/

void dispString(void)
{

printf("String : ");
while(ptr != NULL)
{
printf("%c",ptr->st);
}
printf("\n");

}

#endif

/*
* This funcion checks for palindrome
*
* \param void
* \return BOOL indicates palindrome or NOT
*
*/

BOOL checkPalindrome(void)
{
LIST_t *ptr1 = NULL, *ptr2 = NULL;
BOOL bContinue = TRUE;

/*
* Find the middle of linked list by fast runner/slow runner method
* slwptr Points to (n/2) + 1 when loop exits
*/

while((NULL != fstptr) && (FALSE != bContinue))
{
if(fstptr != NULL)
{
fstptr = fstptr->link; /* Avoid chance of NULL pointer dereferencing */
}
else
bContinue = FALSE;

}

/*
* create another list of length (n/2) and copy items from
* the middle of existing one.
* Implements SECOND linked list as STACK
*/

ptr2 = slwptr;
while(ptr2 != NULL)
{
pCur = (LIST_t *)malloc(sizeof(LIST_t));
pCur->st = ptr2->st;

/* create first node */
else

pPrev = pCur;

}

bContinue = TRUE; /* Reset flag here */

/* Check the two linked lists */
while((NULL != ptr1) && (NULL != ptr2))
{
if(ptr1->st != ptr2->st)
{
bContinue = FALSE;
break;
}
}

return bContinue;

}

int main(void)
{
LIST_t *pCur = NULL, *pNext = NULL;
BOOL bCheck = FALSE;

createString();
// dispString();
{
bCheck = checkPalindrome();
if(bCheck)
printf("PALINDROME\n");
else
printf("NOT PALINDROME\n");

/* free allocated memory */
/* free LIST 1 */
while(pCur != NULL)
{
free(pCur);
pCur = pNext;
}

/* free LIST 2 */
while(pCur != NULL)
{
free(pCur);
pCur = pNext;
}
}
else
printf("You entered NULL string\n");
return 0;

}

Comment hidden because of low score. Click to expand.
0

Please Note :- The above code works for even multiword string.
Palindrome check is case sensitive
For example : Malayalam (NOT PALINDROME)
malayalam (PALINDROME)

More variables are used deliberately for better understanding.You can remove if you wish to.

Comment hidden because of low score. Click to expand.
0
of 0 vote

->traverse input string from first to last element
1. one insert element at head
2. other insert element at tail
-> check whether both the list are same or not.
-> if yes, palindrom else NOT!!!

Comment hidden because of low score. Click to expand.
0
of 0 vote

copy the contents of the original list in reverse order into another linked list using recursion...then match the node values of original list and the new reversed list by taking two pointers...first for original list and second pointer for second(reversed) list by moving both pointers simultaneously one- one step....if somewhere the node values doesn't match then return and display the msg not a pallindrome....

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class Palindrome {
public static void main(String[] args) {
if(isPalindrome(list))
System.out.println("It is Palindrome");
else
System.out.println("It is not a Palindrome");
}

boolean ret=false;
{
}
else{
}
return ret;
}``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Get the length of the link list.
2. Push the nodes of the list to stack from beginning till length/2.
3. Pop-up from stack & keep comparing till end of the list from length/2+1.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>

struct node
{
char a;
};
{
struct node *temp,*r;
temp=*a;

if(*a==NULL)
{
temp=malloc(sizeof(struct node));
temp->a=ab;
*a=temp;
}
else
{
temp=*a;
{
}
r=malloc(sizeof(struct node));
r->a=ab;

}
}
void palindrome(struct node *a)
{
struct node *temp,*mid;
int i,flag=0;
mid=a;
temp=a;
int count=0;
while(a!=NULL)
{
count++;
}

int p=(count)/2;
for(i=0;i<p;++i)
{
}

for(i=0;i<p;++i)
{
if((mid->a)==(temp->a))
{
flag=0;
}
else{flag=1;}

}
if(flag==0)printf("the string is palindrome ");
else
printf("the string is not palindrome ");
}

void main()
{
struct node *p;
p=NULL;

palindrome(p);

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

1.find the number of nodes in the node.
2.now design a function to get the kth element from end.
3.now compare kth element from start and kth element from end till middle is reached.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.sample.que.linkedlist;

public class PalindromeLL {

int counter;

Node newNode = new Node(data);

if (currentNode == null) {
counter++;
return;
}

while (null != currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
counter++;
return;
}

public char getNode(int index) {
if (index < 0) {
return '\0';
}

for (int i = 0; (i < index && currentNode != null); i++) {
currentNode = currentNode.next;
}
System.out.println("\n");
return currentNode.data;

}

public int getNodeCount() {
return counter;
}

public boolean isPalindrome() {
int i = 0;
int j = getNodeCount() - 1;

boolean checkPalin = false;

while (i <= j) {
if (getNode(i) == getNode(j)) {
checkPalin = true;
}else{
checkPalin = false;
break;
}

i++;
j--;
}
return checkPalin;
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````package com.sample.que.linkedlist;

public class PalindromeLL {

int counter;

Node newNode = new Node(data);

if (currentNode == null) {
counter++;
return;
}

while (null != currentNode.next) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
counter++;
return;
}

public char getNode(int index) {
if (index < 0) {
return '\0';
}

for (int i = 0; (i < index && currentNode != null); i++) {
currentNode = currentNode.next;
}
System.out.println("\n");
return currentNode.data;

}

public int getNodeCount() {
return counter;
}

public boolean isPalindrome() {
int i = 0;
int j = getNodeCount() - 1;

boolean checkPalin = false;

while (i <= j) {
if (getNode(i) == getNode(j)) {
checkPalin = true;
}else{
checkPalin = false;
break;
}

i++;
j--;
}
return checkPalin;
}

}``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.