Make palindrome of link list's element

Question

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

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

Please give most optimize code?

Comments

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

Answer 1

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).

Comments

So finally you reverse the list.  :)
but not answered the question. :)

Answer 2

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 3

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.

Comments

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.

Answer 4

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

Comments

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.