Linked List: Program to check the nodes form a palindrome

Write a program to check if a linked list nodes form a palindrome expression

Approach

• A palindrome is an expression or sequence that reads the same backward as forward. For e.g. 'madam' or 'refer' or '123321'
• To check if the linked list elements form a palindrome or not,the approach is to push all elements of the linked list from the head into the stack
• Then iterate throught the linkedlist and pop one element from stack and checked whether its equal to linked list element
• The idea is to check the first element with the last element and since stack has the property of last in first out, we will have the last element at the top of stack

Algorithm

1. If the head is NULL then simply return
2. Create a stack for storing linked list elements andcreate pointers, say current and set on head
3. While current is not NULL, push all elements of linked list one by one into the stack
4. Again set current on head and initialise flag to 0
5. While current is not NULL and stack is not empty, pop one element from stack and check if current.data is not equal, then simply print linked list is not palindrome and set flag=1 and exit from loop
6. After the loop ends, if the flag is equal to zero that means the linked list is palindrome

Complexity

Time Complexity : O(n) , where n is the number of nodes in linked list
Space Complexity : O(n) , where n is the number of nodes in linked list

Java Code

   import java.util.*;

    class CheckLLPalindrome{
        
        class Node {
            int data;
            Node next;
         
            Node(int d) {
                this.data = d;
                this.next = null;
            }
        }
        
        Node head;
     
        // creating a linked list using array
        public void buildLinkedlist(int A[], int noOfNodes) {
            int i;
            Node temp, last;
            temp = new Node(A[0]);
            temp.next = null;
            head = temp;
            last = temp;
            for (i = 1; i < noOfNodes; i++) {
                temp = new Node(A[i]);
                temp.next = null;
                last.next = temp;
                last = temp;
            }
        }
     
        // printing of linkedList
        public void printLinkedlist() {
            List allNodesList = new ArrayList<>();
            Node temp = head;
            while (temp != null) {
                allNodesList.add(Integer.toString(temp.data));
                temp = temp.next;
            }
            System.out.println(String.join(" -> ", allNodesList));
        }
     
        // function to calculate length of linked list
        public int getLength() {
            Node temp = head;
            int count = 1;
            while (temp.next != null) {
                temp = temp.next;
                count++;
            }
            return count;
        }
     
        // function to check whether linked list is palindrome or not
        public void isPalindrome() {
            if(head == null)
                 return;
    
            Stack stack = new Stack();
            Node current = head;
            
            while (current != null) {
                stack.push(current.data);
                current = current.next;
            }
            
            int flag = 0;
            current = head;
            
            while (current != null && !stack.isEmpty()) {
                int element = stack.pop();
                
                if (current.data != element) {
                    System.out.println("Given Linked is not palindrome");
                    flag = 1;
                    break;
                }
                current = current.next;
            }
            
            if (flag == 0)
                System.out.println("Given Linked is palindrome");
     
        }
     
        public static void main(String[] args) {
            int[] linkedlistElements = new int[] { 1, 2, 3, 3, 2, 1};
            int numberOfNodes = linkedlistElements.length;
            
            CheckLLPalindrome ll = new CheckLLPalindrome();
            ll.buildLinkedlist(linkedlistElements, numberOfNodes);
            
            System.out.println("Given Linked List ");
            ll.printLinkedlist();
            ll.isPalindrome();
        }
    }

Output

Given Linked List
1 -> 2 -> 3 -> 3 -> 2 -> 1
Given Linked is palindrome