The Gateway to Computer Science Excellence
+1 vote
320 views
1) What is the algorithm for reversing the singly linked list?

2) How palindrome could be made with the help of this algo ?
in Algorithms by Veteran (117k points) | 320 views
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.

2 Answers

+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

by Boss (18.3k points)
edited by
+1
yes, I have done it by braking the list from middle
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)
by Veteran (117k points)

Related questions

0 votes
1 answer
2
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,647 questions
56,508 answers
195,530 comments
100,969 users