How to Check Given LinkedList is Palindrom or Not? | Recursive and Two Pointer Approach with Explanation

Check Palindrome Linked List using Recursive and Two Pointer Approach in Java with Explanation

Problem Description :

Given the head of a singly linked list, return true if it is a palindrome.

Example 1 :

Input : head = [1, 2, 2, 1]
Output : true

Example 2 :

Input : head = [1, 2, 3, 2, 1]
Output : true

Example 3 :

Input : head = [1, 2, 3, 4, 5, 6]
Output : false

Example 4 :

Input : head = [6, 5, 4, 4, 6, 5]
Output : false

Solution 1 : Find LinkedList is Palindrome or not using Recursion in Java

import java.util.Scanner;

public class PalindromeLinkedList {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        System.out.println("Enter Size of LinkedList");
        int size = sc.nextInt();
        
        System.out.println("Enter Data in LinkedList");
        
        // Creating CustomLinkedList object and storing Node
        CustomLinkedList list = new CustomLinkedList();
        for (int i = 0; i < size; i++) {
             list.insert(sc.nextInt());
        }
        
        System.out.println(checkPalindrom(list));
    }

    static Node nodeRef;
    static boolean checkPalindrom(CustomLinkedList list) {
        nodeRef = list.head;
        return isPalindrom(list.head);
    }
    
    static boolean isPalindrom(Node node) {
        if (node == null) {
            return true;
        }
        
        boolean ans = isPalindrom(node.next);
        boolean isEqual = node.value == nodeRef.value ? true : false;

        nodeRef = nodeRef.next;
        return ans && isEqual;
    }
}

 class Node {
    
    //Data in the current node
    int value;
    //Reference for the next node
    Node next;

    Node(int value) {
        this.value = value;
    }
}

 class CustomLinkedList {
    
    Node head;

    public void insert(int value) {
        Node newNode = new Node(value);
        
        if (head == null) {
            head = newNode;
        } else {
            Node n = head;
            while(n.next != null) {
                n = n.next;
            }
            n.next = newNode;
        }
    }
}

Solution Explanation :

• First take reference of head in temporary node. So we can use while comparing nodes value.
• Call recursive method isPalindrom() with reference of head node.  
• In isPalindrom() method,
• Create base case, If current node is null return true. It will use for get last node of LinkedList.
  
• Call recursion function isPalindrom() and store answer in ans variable.
• Check both side of value one by one and store ans in isEqual variable.
• Store next value of node in nodeRef variable.
• Return true if both ans and isEquals variable is true otherwise it will returns false.

Solution 2 : Find Given LinkedList is Palindrom or Not using Two Pointer Approach

private static boolean checkPalindrom(Node head, Node last) {

    Node slow = head;
    Node fast = head;
    Node reverse = null;

    while (fast != null && fast.next != null) {
        Node node = new Node(slow.value);

        // Reversing LinkedList from 0 to middle
        node.next = reverse;
        reverse = node;

        slow = slow.next;
        fast = fast.next.next;
    }

    // Used when LinkedList size is odd (ex. 3,5,7,...)
    if (fast != null) {
        slow = slow.next;
    }

    // Comparing values of first and second half
    while (slow != null) {
        if (slow.value != reverse.value) {
            return false;
        }

        slow = slow.next;
        reverse = reverse.next;
    }

    return true;
}

Solution Explanation :

• Defining three Node references,
• slow = It will traverse from start to mid Node of linked list. after that it will use for comparing values from mid to end with reversed list.
  
• fast = It will traverse through entire linked list from start to end (It is used for get mid of Node of linked list).
• reverse = It will reverse values from start to mid. (In linked list, only next pointer change for reversing).
• In first while loop, reverse linked list from start to mid. (ex. list size = 8, mid = 4 | list size = 5, mid = 3)
  
• Second while loop used only list size is odd (3,5,7,...). Here, assign next Node of mid to slow. (ex. list size = 7 , mid = 4 so we do not have to compare mid value to any other value).
• In third while loop, compare reversed value (start to mid) with slow pointer (mid to end).

   

RECOMMENDED ARTICLES :

1. Merging two sorted Linked List using Recursion approach with Stack trace 
2. 4 Ways to find Given Number is Power of Two or Not in Java and Python
3. Print Length of Longest Substring Without Repeating Characters from given String using Sliding Window Algorithm 
4. Find All Numbers that are not present in Java Array from 1 to n