   # Make palindrome of link list's element

+3 votes
198 views

Link List ??
A -> B -> C -> D -> E

OUTPUT ;
A -> B -> C -> D -> E -> D -> C -> B -> A

Please give most optimize code? posted Oct 23, 2013
Share this question
1. Reverse the LL
2. Add (original, reverse->next)
Salil, can you elaborate this more ?
Step1: Reverse LL: E, D, C, B, A
Step 2: Concat LL + Reverse LL->next (omit first element as it is already there in LL)
And you are done.
I think there is some thing wrong.
when we reverse LL we update the next pointer only.
so we will lost "Concat LL".
Please correct If I am wrong.
LL = A B C D E
Rev LL = E D C B A
Rev LL->next = D C B A
Palindrome = concat (LL, Rev LL) = A B C D E D C B A

## 4 Answers

0 votes

Best answer

1) set a pointer(tail) to last element(in your example it is 'E').
2) now start from head and append this node to the next of tail pointer, (since tail pointer is pointing to the E so element(A) will be appended next to E)
Now your LL would look like A->B->C->D->E->A
3) now move head pointer to the next element (so this time head is pointing to the node 'B' ) and tail pointer is still pointing to 'E'.
4) now repeat step 2 and three untill (head pointer== tail pointer). answer Oct 23, 2013 by anonymous
So finally you reverse the list.  :)
but not answered the question. :)
+1 vote
``````end = make_palindrome(head);
end->next = NULL;

struct node *make_palindrome(struct node *head)
{
struct node *tmp, *ptr;
if(!head->next)
return head;

ptr = make_palindrome(head->next);

tmp = (struct node *)malloc(sizeof(struct node));
tmp->data = head->data;
ptr->next = tmp;

return tmp;
}
`````` answer Oct 24, 2013
–1 vote

you wanted to do the process in same list? OR can I make separate list with palindrome ?

For Ex, Assume input in one list call LIST1, then I will create LIST2 that will contain palindrome. answer Oct 23, 2013 by
Do not mind, but It is not answer.
I did not shared answer yet. I am waiting for anuj reply for my question that whether I can use new structure or not.  .
But you clicked on answer .
Please do not asked question in block for answer.
You can use comment.
oh ya. I do mind here after.
–1 vote

It took memory but time consumption will be less.

Create a temp list and traverse the main list using recursive, make copy of each node while traversing.

HEAD *temp;

fun(HEAD *main)
{
if(main == NULL)
return NULL
make_copy(temp, main); // have to move temp to temp->next
fun(main->next);
make_copy(temp, main); // have to move temp to temp->next
}

print(temp); answer Oct 23, 2013 by
This will not work i guess because you are passing the address only
and not returning the address. So changes in function make_copy will not reflect.
Can you please write the code of make_copy.
This is just an upper level code. I agree. But it should work with call by reference.
Similar Questions
+8 votes

Convert the given string into palindrome with minimum number of appends(at end of the given string). O(n) algorithm will be appreciated ??

Input :=> Malayal
Output :=> Malayalam

+7 votes

Input:
First List: 5->6->3 // represents number 563
Second List: 8->4->2 // represents number 842
Output
Resultant list: 4->7->4->0->4->6 // represents number 474046

+5 votes

Help me to write a C program which can generate list of numbers which are palindrome in decimal and octal notion. You can take some max as a limit find out all numbers which satisfy the given property between 1 to n.

+5 votes

WAP to Check whether a Singly Linked List is a Palindrome ??
time complexity should be O(n) ??

+4 votes
``````List => 1 --->  2 --->  3 --->  4 ---> 5 ---> 6
/        \
10          7
\          /
9 <---  8

OURTPUT => 1 --->  2 --->  3 --->  4 ---> 10 ---> 9
/        \
5           8
\          /
6 <---  7
``````