Recursively check if the linked list of characters is palindrome or not
Given a linked list of characters, recursively check if it is palindrome or not.
For example,
Output: The linked list is a palindrome
Input: A —> B —> C —> C —> B —> null
Output: The linked list is not a palindrome
The idea is to recursively traverse until the end of the linked list and construct a string out of the nodes’ characters in visited order. Then as the recursion unfolds, build another string from the linked list nodes, but this time, the encountered order of processed nodes is the opposite, i.e., from the last node towards the head node. If both constructed strings are equal, we can say that the linked list is a palindrome.
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include <iostream> using namespace std; // A Linked List Node struct Node { char data; Node* next; Node(char ch) { this->data = ch; this->next = nullptr; } }; // Construct 's1' and 's2' out of the given linked list with consecutive // list elements in the forward and backward direction void construct(Node* &head, string &s1, string &s2) { // base case if (head == nullptr) { return; } s1 += head->data; construct(head->next, s1, s2); s2 += head->data; } // Function to check if a given linked list of characters is a palindrome bool isPalindrome(Node* head) { // construct string 's1' and 's2' with consecutive elements of the linked list // starting from the beginning and the end string s1, s2; construct(head, s1, s2); // check if the linked list is a palindrome return s1 == s2; } int main() { Node* head = new Node('A'); head->next = new Node('B'); head->next->next = new Node('C'); head->next->next->next = new Node('B'); head->next->next->next->next = new Node('A'); if (isPalindrome(head)) { cout << "Linked List is a palindrome."; } else { cout << "Linked List is not a palindrome."; } return 0; } |
Output:
Linked List is a palindrome.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
// A Linked List Node class Node { char data; Node next; Node(char ch) { this.data = ch; this.next = null; } } class Main { // Construct 's1' and 's2' out of the given linked list with consecutive // list elements in the forward and backward direction public static void construct(Node head, StringBuilder s1, StringBuilder s2) { // base case if (head == null) { return; } s1.append(head.data); construct(head.next, s1, s2); s2.append(head.data); } // Function to check if a given linked list of characters is a palindrome public static boolean isPalindrome(Node head) { // construct string 's1' and 's2' with consecutive elements of the linked list // starting from the beginning and the end StringBuilder s1 = new StringBuilder(), s2 = new StringBuilder(); construct(head, s1, s2); // check if the linked list is a palindrome return s1.toString().equals(s2.toString()); } public static void main(String[] args) { Node head = new Node('A'); head.next = new Node('B'); head.next.next = new Node('C'); head.next.next.next = new Node('B'); head.next.next.next.next = new Node('A'); if (isPalindrome(head)) { System.out.println("Linked List is a palindrome."); } else { System.out.println("Linked List is not a palindrome."); } } } |
Output:
Linked List is a palindrome.
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
# A Linked List Node class Node: def __init__(self, ch): self.data = ch self.next = None # Construct 's1' and 's2' out of the given linked list with consecutive # list elements in the forward and backward direction def construct(head, s1='', s2=''): # base case if head is None: return s1, s2 s1 += head.data s1, s2 = construct(head.next, s1, s2) s2 += head.data return s1, s2 # Function to check if a given linked list of characters is a palindrome def isPalindrome(head): # construct string 's1' and 's2' with consecutive elements of the linked list # starting from the beginning and the end (s1, s2) = construct(head) # check if the linked list is a palindrome return s1 == s2 if __name__ == '__main__': head = Node('A') head.next = Node('B') head.next.next = Node('C') head.next.next.next = Node('B') head.next.next.next.next = Node('A') if isPalindrome(head): print('Linked List is a palindrome.') else: print('Linked List is not a palindrome.') |
Output:
Linked List is a palindrome.
We can even determine if a linked list is a palindrome or not without constructing a string out of characters. This can be done recursively by comparing the data at the first node with the last node, the data at the second node with the second last node, etc.
We can do this with the use of two head pointers as parameters to the recursive function. The idea is to recursively advance the second pointer until the end of the linked list is reached. When the recursion unfolds, compare the character pointed by the first pointer with that of the second pointer. If at any point the characters don’t match, the linked list cannot be a palindrome. To keep the left pointer in sync with the right pointer, advance the left pointer to the next node after each recursive call.
Following is the C++, Java, and Python implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
#include <iostream> using namespace std; // A Linked List Node struct Node { char data; Node* next; Node(char ch) { this->data = ch; this->next = nullptr; } }; // Recursive function to check if a given linked list of characters is // a palindrome. Note that the left pointer is passed by reference, and // the right pointer is just a copy. bool isPalindrome(Node*& left, Node* right) { // Base case if (right == nullptr) { return true; } // Return false on the first mismatch if (!isPalindrome(left, right->next)) { return false; } // Copy the left pointer Node* prevLeft = left; // Advance the left pointer to the next node. // This change would reflect in the parent recursive calls. left = left->next; // For the linked list to be a palindrome, the character at the left // node should match with the character at the right node return (prevLeft->data == right->data); } int main() { Node* head = new Node('A'); head->next = new Node('B'); head->next->next = new Node('C'); head->next->next->next = new Node('B'); head->next->next->next->next = new Node('A'); if (isPalindrome(head, head)) { cout << "Linked List is a palindrome."; } else { cout << "Linked List is not a palindrome."; } return 0; } |
Output:
Linked List is a palindrome.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
// A Linked List Node class Node { char data; Node next; Node(char ch) { this.data = ch; this.next = null; } } class Main { // Wrapper over `Node` class static class NodeWrapper { public Node node; NodeWrapper(Node node) { this.node = node; } } // Recursive function to check if a given linked list of characters is a palindrome public static boolean isPalindrome(NodeWrapper left, Node right) { // Base case if (right == null) { return true; } // Return false on the first mismatch if (!isPalindrome(left, right.next)) { return false; } // Copy the left child Node prev_left = left.node; // Advance the left child to the next node. // This change would reflect in the parent recursive calls. left.node = left.node.next; // For the linked list to be a palindrome, the character at the left // node should match with the character at the right node return (prev_left.data == right.data); } public static void main(String[] args) { Node head = new Node('A'); head.next = new Node('B'); head.next.next = new Node('C'); head.next.next.next = new Node('B'); head.next.next.next.next = new Node('A'); // Wrap node, so its reference can be changed inside `isPalindrome()` NodeWrapper left = new NodeWrapper(head); if (isPalindrome(left, head)) { System.out.println("Linked List is a palindrome."); } else { System.out.println("Linked List is not a palindrome."); } } } |
Output:
Linked List is a palindrome.
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
# A Linked List Node class Node: def __init__(self, data=None, next=None): self.data = data self.next = next # Recursive function to check if a given linked list of characters is a palindrome def isPalindrome(left, right): # Base case if right is None: return True, left # Return false on the first mismatch val, left = isPalindrome(left, right.next) if not val: return False, left # Copy the left child prev_left = left # Advance the left child to the next node. # This change would reflect in the parent recursive calls. left = left.next # For the linked list to be a palindrome, the character at the left # node should match with the character at the right node return prev_left.data == right.data, left if __name__ == '__main__': head = Node('A') head.next = Node('B') head.next.next = Node('C') head.next.next.next = Node('B') head.next.next.next.next = Node('A') left = head if isPalindrome(left, head)[0]: print('Linked List is a palindrome.') else: print('Linked List is not a palindrome.') |
Output:
Linked List is a palindrome.
The time complexity of both above-discussed methods is O(n), where n is the length of the linked list. The auxiliary space required by the program for the call stack is proportional to the lists’ length.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)