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:
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 pointer ‘ptr’ 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.
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.
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.
Related
Contributed by