FOR FREE YEAR SOLVED

Before starting the program we need to know about the structure of each node of the linked list. The structure of each node of the linked list is:

Each node contains two parts:

• Data part
• Address Part

And the node can be represented as:

Here the program is written to check whether a list is a palindrome or not.

To perform this program the input is taken as a string. Then each character of the string is inserted at each node of the list.

Let the list after inserting the characters are:

First, a pointer is pointed at the first node of the list. A null string is defined to store the characters while traversing the list. The character of the node will be concatenated and will be stored in the string.

The character of the first node is a. Therefore, ‘a’ will be concatenated with the null string. The string after concatenation is “a”.

Now, the pointer ‘ptr’ will be pointing to the next node of the list.

The character at this node is ‘b’ which will now be again concatenated with the string. The string now becomes “ab”.

The pointer will be moved to the next node.

The character of this node is ‘a’. It will be concatenated with the string which makes the string “aba”.

Now, this string will be reversed and will be compared. If the string and the reverse of the string are equal then the list of characters is palindrome otherwise not.  

INPUT: A string of which the characters is to be inserted in the list and checked for palindrome.
OUTPUT:  a) The list after creating it.
	        b) Whether the list is a palindrome or not.
PROCESS:
Step 1: Define a structure named ‘node’ which has two parts−
•	The data part of character type.
•	The ‘next’ (points to it’s next node i.e. the address of the next node) part which is a structure (node) type pointer.
Step 2: Create a function “void createlist()”:
Step 2.1: Take the string from user and store the length of the string in ‘n’ 
Step 2.2: For i=0 to (n-1) repeat  Step 2.3 to Step 2.7
Step 2.3: take the character from the string at index ‘i’ and store in ‘x’
Step 2.4: Create a new node in ‘p’(a ‘node’ type pointer) by using ‘malloc’ function.                    
Set data[p] <- x
	          Set next[p] <- Null
Step 2.5: If (head1 = Null) then
                     		Set head1 <- p
	           [End of ‘If’]
Step 2.6: Else   
            		Set next[ptr] <- p
	            [End of ‘Else’] 

Step 2.7: Set ptr <-p

                [End of  Step 2.2 ‘For’ loop]
[End of  the function “void createlist( )”]   
Step 3: Create a function “void displaylist()”
	Step 3.1: Set p <-head1
	Step 3.2: While(p≠Null) then repeat Step 3.3 and Step 3.4
	Step 3.3: Print  data[p]
	Step 3.4: Set p<-next[p]	
[End of  Step 3.2 ‘While’ loop]
[End of  the function “void displaylist( )”]
Step 4: Create a function “void palindrome()”
	Step 4.1: Set p<-head1
	Step 4.2: Set i<-0
	Step 4.3: while p≠NULL then repeat Step 4.4 and Step 4.6
	Step 4.4: Set a[i]<-data[p]
	Step 4.5: Set p<-next[p]
	Step 4.6: Set i<-i+1
	[End of Step 4.3 ‘while’ loop]
	Step 4.7: Copy the string ‘a’ into a string ‘b’
	Step 4.8: Reverse the string ‘b’ and store in the string ‘b’.
	Step 4.9: if string a = string b then
	   print "Palindrome"
	      else
	   print "Not a Palindrome"
	[End of Step 4.9 ‘if’]
[End of the function ‘palindrome()’]
Step 5: [Function ‘main()’]
	Call the function ‘createlist()’
	Call the function ‘displaylist()’
Call the function ‘palindrome()’
Step 6: Stop.