Check If a Linked List is Palindrome or Not in Java

Hello coders, Welcome to codingbroz where we help you learn coding concepts. Today we are here to discuss another coding interview problem on linked list data structure.

Today we are going to discuss a program to check if a linked list is Palindrome or not !

Prerequisites :

Before moving towards solving this linked list problem you need to have knowledge about two linked list concepts. These are as follows :

1. Find Middle of a linked list
2. How to reverse a linked list

Problem Statement :

You are given an Linked List of Integer, check whether the given linked list is Palindrome or not. (check if a linked list is Palindrome or not)

Input :

1->2->3->4->3->2->1->null
1->2->3->4->2->1->null

Output :

true
false

Approach : Check if a linked list is Palindrome or not

1. find the middle node
2. reverse the sub list from next of the middle node
3. compare each node from sub list 1 and sub list 2
4. If any node differs then print "false" otherwise print "true" 

Program to check if a linked list is palindrome or not :

import java.util.*;

class Main {
    public static class ListNode {
        int val = 0;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    
    public static ListNode midNode(ListNode head){
        if(head==null || head.next == null)return head;
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next!=null && fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    
    public static ListNode reverseList(ListNode head){
        if(head==null || head.next==null)return head;
        ListNode prev = null;
        ListNode cur = head;
        ListNode nNode = null;
        
        while(cur != null){
            nNode = cur.next;// backup
            cur.next = prev;//link
            prev = cur;
            cur = nNode;
        }
        return prev;
    }
    
    public static boolean isPalindrome(ListNode head) {
        if(head==null || head.next==null) return true;
        ListNode mid = midNode(head);
        ListNode nHead = mid.next;//head of sublist2
        mid.next = null;//breaking the list in sublist1
        
        nHead = reverseList(nHead);//reversing sublist2
        
        ListNode c1 = head;
        ListNode c2 = nHead;
        boolean res = true;
        while(c2!=null){
            if(c1.val!=c2.val){
                res = false;
                break;
            }
            c1 = c1.next;
            c2 = c2.next;
        }
        
        return res;
    }

    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt();
        ListNode dummy = new ListNode(-1);
        ListNode prev = dummy;
        while (n-- > 0) {
            prev.next = new ListNode(scn.nextInt());
            prev = prev.next;
        }

        System.out.println(isPalindrome(dummy.next));
    }
}

The following solution is to check if a linked list is palindrome or not.

Now, Let’s talk about the time complexity of the given solution to check if a linked list is palindrome or not !

Time Complexity : n/2 + n/2 + n/2 +n = 5n/2

If we talk in terms of Big-O, then the time complexity of the code is O(n) and the space complexity of the code is constant as no extra space has been used.

More Interview Problems on Linked List

Today you learned to Check if a linked list is palindrome or not. Here are some more Coding Interview Problems on Linked List data structure you must try. These are as follows :

1. Fold a Linked List
2. Unfold a Linked List
3. Merge Two sorted Linked list
4. Merge Sort a Linked List
5. Remove Nth from end of linked list
6. Segregate even and odd nodes in a linked list