0 votes
477 views
in Data Structure And Algorithm by
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

3 Answers

0 votes
by (5k points)
edited by
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
0 votes
by (5k points)
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;
    }
0 votes
by (5k points)
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;
    }

Share:- Whatsapp Facebook Facebook


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

Categories

...