• Register
Welcome to Developerhelpway Q&A, where you can ask questions and receive answers from other members of the community.

Check if linked list is palindrome or not in java

0 votes
19 views
Function to check a linked list is palindrome or not in java.
List:- [R E F E R]
Output:- R E F E R Palindrome
asked Jan 23 in Data Structure And Algorithm by Ajay Pawar

3 Answers

0 votes
package com.dev.ds;

import java.util.Stack;

public class CheckLinkedListPalindrome {

    Node head;
   
    public static void main(String[] args) {
        CheckLinkedListPalindrome p = new CheckLinkedListPalindrome();
        p.insert("R");
        p.insert("A");
        p.insert("D");
        p.insert("A");
        p.insert("R");
        //p.insert("P");
       
        p.print();
       
        boolean b = p.linkedListPlaindrome(p.head);
        if(b){
            System.out.println("Palindrome");
        }else{
            System.out.println("Not Palindrome");
        }
       
    }
   
    private class Node{
        String data;
        Node next;
        Node(String data){
            this.data = data;
        }
    }
   
    /**
     *
     * Time Complexity O(n)
     * Space Complexity O(n)
     *
     * @param head
     * @return
     */
    public boolean linkedListPlaindrome(Node head){
        if(head==null)
            return false;
        Stack<Node> stack = new Stack<>();
        Node curr = head;
        while(curr != null){
            stack.push(curr);
            curr = curr.next;
        }
        curr = head;
        while(curr != null){
            if(!curr.data.equals(stack.pop().data)){
                return false;
            }
            curr = curr.next;
        }
        return true;
    }
   
    public void insert(String data){
        Node newNode = new Node(data);
        if(head == null){
            head = newNode;
        }else{
            Node curr = head;
            while(curr.next != null){
                curr = curr.next;
            }
            curr.next = newNode;
        }
    }
   
    public void print(){
        if(head==null)
            return;
        Node curr = head;
        while(curr != null){
            System.out.print(curr.data + " ");
            curr = curr.next;
        }
    }

}
Output: - R A D A R Palindrome
answered Jan 26 by ranju_12 (1,740 points)
edited Jan 26 by ranju_12
0 votes
See the following method to check given linked list is palindrome or not.

Following function returns true if linked list is palindrome otherwise return false.

/**
     *
     * Time Complexity O(n)
     * Space Complexity O(n)
     *
     * @param head
     * @return
     */
    public boolean isPalindrome(Node head){
        if(head == null)
            return false;
        Node current = head;
        Node rev = null;
        while(current != null){
            Node temp = new Node(current.data);
            temp.next = rev;
            rev = temp;
            current = current.next;
        }
        current = head;
        while(current != null){
            if(current.data != rev.data)
                return false;
            rev = rev.next;
            current = current.next;
        }
        return true;
    }
answered Jan 26 by ranju_12 (1,740 points)
0 votes
See the following linked list example which express you to how to check linked list is palindrome or not.

Bellow example used two pointers. One for fast traversal. The faster pointer jumped two node at once iteration but slow pointer traverse one by one.

    /**
     * This is faster but needed two pointers
     *
     * @param head
     * @return
     */
    public boolean isPalindromeUsingTwoPointers(Node head){
        if(head == null)
            return false;
        Node slow = head;
        Node fast = head;
        while(fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        Node secondHalf = slow.next;
        slow.next = null;
        //reverse second part of the list
        Node p1 = secondHalf;
        Node p2 = p1.next;
        return true;
    }
answered Jan 26 by ranju_12 (1,740 points)
...