FOR FREE MATERIALS

Check whether a list is a Palindrome or not

Back to Programming

Description

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.

Let the existing list be:

 

 

Now, it has to be checked whether the list is a palindrome or not.

First a variable of integer type should be taken initialized with 0. A pointer is to be taken which will first point to the first node of the list.

 

 

The value of the variable of integer type will be calculated such as it contains the number containing all the digits of the linked list. First, the value of the variable will be 1 as the first element of the list is ‘1’.

Now, the pointerptr’ will be pointing to the next node of the list.

 

 

Again, the same process will be repeated and the value of the variable will become 12.

The pointer will now be pointing to the last node of the list.

 

 

Now, the value of the variable will be 121. This process is continued till the last node of the list. For this program, the element of the list should be a single digit number. Now the value of the integer variable will be reversed and then they will be compared. If the value and the reversed value are the same then the list is a palindrome otherwise the list is not a palindrome.

Algorithm

INPUT:  The number of elements to create the list and the elements which are to be inserted 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 integer 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 number of  elements from user in an ‘integer’ type variable ‘n’
 Step 2.2: For i=0 to (n-1) repeat  Step 2.3 to Step 2.7
 Step 2.3: Take the element which is to be inserted in an integer type variable  ‘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 n<-0 and Set m<-0
 Step 4.3: while p≠NULL repeat step 4.4 and 4.5
 Step 4.4: Set n<-(n×10)+data[p]
 Step 4.5: Set p<-next[p]
	[End of Step 4.3 ‘while’ loop]
 Step 4.6: Set tmp<-n
 Step 4.7: while tmp>0 repeat Step 4.8 and 4.9
 Step 4.8: Set m<-(m×10)+(tmp modulus 10)
 Step 4.9: Set tmp<-tmp/10
	[End of Step 4.7 ‘while’ loop]
 Step 4.10: if m=n then
			Print "Palindrome"
		     else
			print "Not a Palindrome"
	[End of step 4.10 ‘if’]
[End of function ‘palindrome()’]

Step 5: [Function ‘main()’]
	Call the function ‘createlist()’
	Call the function ‘displaylist()’
Call the function ‘palindrome()’

Step 6: Stop. 

Code

ADVANTAGES:

1. The memory is allocated dynamically i.e. at the runtime. So, there is no limit to the number of digits that is to be checked as a palindrome.

 

2. There is no wastage of memory as the number of nodes is only created according to our needs. No extra memory spaces are allocated.

 

DISADVANTAGES:

1. Another method of palindrome checking can be done by comparing the 1st element with the last element, the 2nd element with the 2nd last element, and so on in the case of an array which is not possible in the case of a singly linked list as reversed traversing is not possible.

 

TIME COMPLEXITY

The time complexity to make the number from the digits of the list is O(n) if n is the number of elements of the list. 

And for reversing the number it takes O(m) time where m is the number of digits of the number.

 

SPACE COMPLEXITY

The space complexity of this program is O(n) if n is the number of elements of the list.

Contributed by