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

2) How palindrome could be made with the help of this algo ?
0
making palindrome means?
0
means to check a string is pallindrome or not.

That means come to the middle of the linked list and then chk if first half and second half is same or not.

I cannot understand how this could be done in singly linked list
0
You write a C code and do a traversal of linked list - print all elements. Then paste it as an answer here.
3
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.
0
For reversing a singly list you would need three pointers namely; previous, current and next.

1 vote

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
1
yes, I have done it by braking the list from middle
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

1
320 views
Suppose there are two singly linked lists both of which intersect at some point and become a single linked list. The head or start pointers of both the lists are known, but the intersecting node is not known. Also, the number of nodes in each of the lists before they ... n,m < n or m > n. Give an algorithm for finding the merging point. And find the time complexity and space complexity also.