top button
Flag Notify
    Connect to us
      Facebook Login
      Site Registration Why to Join

Facebook Login
Site Registration

Make palindrome of link list's element

+3 votes
158 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 by Anuj Yadav

Share this question
Facebook Share Button Twitter Share Button Google+ Share Button LinkedIn Share Button Multiple Social Share Button
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 by Vikas Upadhyay
–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 sivanraj
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 sivanraj
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
Contact Us
+91 9880187415
sales@queryhome.net
support@queryhome.net
#280, 3rd floor, 5th Main
6th Sector, HSR Layout
Bangalore-560102
Karnataka INDIA.
QUERY HOME
...