Data Structure Linked List

Question

1) What is the algorithm for reversing the singly linked list?

2) How palindrome could be made with the help of this algo ?

Comments

You write a C code and do a traversal of linked list - print all elements. Then paste it as an answer here.

---

I have an idea.

Since you cannot traverse back in a linked list, we will make use of recursion.

First of all, all we need to do is to identify the middlemost node of the linked list.

If the number of nodes is odd, we have one middle most element. If the number is even, we have two.

Now recursively traverse till the middle element and stop there. During the unwinding phase, keep comparing the keys with the remaining part of the list, till the first node is compared with the last node.

---

For reversing a singly list you would need three pointers namely; previous, current and next.

Answer 1

First make a copy of original list

Then reverse that copy using algorithm explained here

Now to check for palindrome

Take 2 pointers a,b

A points to first element of original list 

B points to first element of reverse list

Data at a = data at B then go to next element 

If data does not match then not palindrome break

Else repeat till end of list

Comments

yes, I have done it by braking the list from middle

Answer 2

First of all I found recursive version of  reversing singly linked list better than iterative version of SLL.

1) In iterative version we just reverse the link of each node, not exchange the value

2) In recursive version we go end of linked list and print that value and go to  prev call , print the value. Again prev call like that

Now, for palindrome there will be two cases

i) Odd length palindrome

ii) Even length palindrome

i)In Odd length palindrome take 2 pointers p and q

p and q both points to the node which head points

Now, each iteration of while loop increment p like p->next->next and q increment like q->next

until we get p->next=NULL

When p->next=NULL

take another pointer new and assign new =q->next->next

Now break the list from new pointer and reverse it from new pointer to the end of list

Means if a list

1->2->3->4->3->2->1

new will point in 3 of list 3->2->1 and reversing we will get 1->2->3

Now, compare 1st list with 2nd list

ii)For even linked list same thing will happen, p and q pointer will increment in same manner, just go until p!=NULL(not p->next!=NULL)