recategorized by
1,216 views
1 votes
1 votes
1) What is the algorithm for reversing the singly linked list?

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

2 Answers

1 votes
1 votes

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

edited by
0 votes
0 votes
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)

Related questions

0 votes
0 votes
2 answers
4