top button
Flag Notify
    Connect to us
      Site Registration

Site Registration

Make palindrome of link list's element

+3 votes
873 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 LinkedIn 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
...