Check if linked list is palindrome or not in java

Question

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

Answer 1

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

Answer 2

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;
    }

Answer 3

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;
    }