search
Log In
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 ?
in Algorithms 400 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


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)

Related questions

0 votes
0 answers
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.
asked Oct 17, 2018 in DS Lakshman Patel RJIT 320 views
1 vote
1 answer
3
2.7k views
What would be the asymptotic time complexity to add a node at the end of singly linked list, if the pointer is initially pointing to the head of the list? (a) O(1) (b) O(n) (c) θ (n) (d) θ (1) Confused between option (b) and (c) .
asked Jul 4, 2018 in Algorithms arya_stark 2.7k views
1 vote
1 answer
4
244 views
Here In this question it is given that we have to perform nlogn decrease key operation and n find operation . 1)Finding an element in the linked list itself takes O(n) and there are N such operations total=O(n2). 2)Decrease key: Find key O(n) + O(1) for decrease=O(n) and there are nlogn such operations: total O(n2logn). Please correct Me : Image :
asked Nov 16, 2017 in Algorithms saxena0612 244 views
...