Code Destine

Problem Statement

You have given a singly linked list. Write a program to find if it is a palindrome.

Example 

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

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

Solution

This problem can be solved in four steps :-

1. Find the middle node of the linked list.
2. Break the given linked list into two separate parts, first starting from the head and ending at the middle node and second starting from the node next to a middle node and ending at the last node of the linked list.
3. Reverse the second half of the linked list.
4. Traverse both linked list together till the end of the list and compare both values of the node, if values are different then return false. If the end of the linked list is reached and all values are similar, then return true.

Program

public class Main {

	public static void main(String[] args) {
		
		ListNode head = null;		
		ListNode node = new ListNode(1);
		head = node;		
		node.next = new ListNode(2);
		node = node.next;		
		node.next = new ListNode(3);
		node = node.next;		
		node.next = new ListNode(3);
		node = node.next;		
		node.next = new ListNode(2);
		node = node.next;		
		node.next = new ListNode(1);	
		
		Main main = new Main();
		boolean result = main.isPalindrome(head);
		System.out.print(result);
	}
	
	/* Solution */
	public boolean isPalindrome(ListNode head) {
        
        ListNode slow = head, fast = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        if (fast != null) {
			slow = slow.next;
		}
        
        ListNode reverseList = reverse(slow);
        
        ListNode temp = head;        
        while(reverseList != null){            
            if(reverseList.value != temp.value){
                return false;
            }
            reverseList = reverseList.next;
            temp = temp.next;
        }
        return true;
    }
    
    public ListNode reverse(ListNode head){        
        ListNode previous = null;
        ListNode current = head;
        ListNode next = null;
        while(current != null){
            next = current.next;
            current.next = previous;
            previous = current;
            current = next;
        }
        return previous;        
    }
	
	/* Definition of Linked List Node */
	public static class ListNode {		
		int value;
		ListNode next;
		
		public ListNode(int value) {
			this.value = value;
		}		
	}
}

Result

true

That’s all for Palindrome Linked List in Java, If you liked it, please share your thoughts in a comments section and share it with others too.