Function to check if a singly linked list is palindrome | Java program to check if linked list is palindrome ; Linked list Node ; head of list ; Function to check if given linked list is palindrome or not ; To handle odd size list ; initialize result ; Get the middle of the list . Move slow_ptr by 1 and fast_ptrr by 2 , slow_ptr will have the middle node ; We need previous of the slow_ptr for linked lists with odd elements ; fast_ptr would become NULL when there are even elements in the list and not NULL for odd elements . We need to skip the middle node for odd case and store it somewhere so that we can restore the original list ; Now reverse the second half and compare it with first half ; NULL terminate first half ; Reverse the second half ; compare ; Reverse the second half again ; If there was a mid node ( odd size case ) which was not part of either first half or second half . ; Function to reverse the linked list Note that this function may change the head ; Function to check if two input lists have same data ; Both are empty reurn 1 ; Will reach here when one is NULL and other is not ; Push a node to linked list . Note that this function changes the head ; Allocate the Node & Put in the data ; link the old list off the new one ; Move the head to point to new Node ; A utility function to print a given linked list ; Driver program to test the above functions ; Start with the empty list
class LinkedList { class Node { char data ; Node next ; Node ( char d ) { data = d ; next = null ; } } Node head ; Node slow_ptr , fast_ptr , second_half ; boolean isPalindrome ( Node head ) { slow_ptr = head ; fast_ptr = head ; Node prev_of_slow_ptr = head ; Node midnode = null ; boolean res = true ; if ( head != null && head . next != null ) { while ( fast_ptr != null && fast_ptr . next != null ) { fast_ptr = fast_ptr . next . next ; prev_of_slow_ptr = slow_ptr ; slow_ptr = slow_ptr . next ; } if ( fast_ptr != null ) { midnode = slow_ptr ; slow_ptr = slow_ptr . next ; } second_half = slow_ptr ; prev_of_slow_ptr . next = null ; reverse ( ) ; res = compareLists ( head , second_half ) ; reverse ( ) ; if ( midnode != null ) { prev_of_slow_ptr . next = midnode ; midnode . next = second_half ; } else prev_of_slow_ptr . next = second_half ; } return res ; } void reverse ( ) { Node prev = null ; Node current = second_half ; Node next ; while ( current != null ) { next = current . next ; current . next = prev ; prev = current ; current = next ; } second_half = prev ; } boolean compareLists ( Node head1 , Node head2 ) { Node temp1 = head1 ; Node temp2 = head2 ; while ( temp1 != null && temp2 != null ) { if ( temp1 . data == temp2 . data ) { temp1 = temp1 . next ; temp2 = temp2 . next ; } else return false ; } if ( temp1 == null && temp2 == null ) return true ; return false ; } public void push ( char new_data ) { Node new_node = new Node ( new_data ) ; new_node . next = head ; head = new_node ; } void printList ( Node ptr ) { while ( ptr != null ) { System . out . print ( ptr . data + " - > " ) ; ptr = ptr . next ; } System . out . println ( " NULL " ) ; } public static void main ( String [ ] args ) { LinkedList llist = new LinkedList ( ) ; char str [ ] = { ' a ' , ' b ' , ' a ' , ' c ' , ' a ' , ' b ' , ' a ' } ; String string = new String ( str ) ; for ( int i = 0 ; i < 7 ; i ++ ) { llist . push ( str [ i ] ) ; llist . printList ( llist . head ) ; if ( llist . isPalindrome ( llist . head ) != false ) { System . out . println ( " Is ▁ Palindrome " ) ; System . out . println ( " " ) ; } else { System . out . println ( " Not ▁ Palindrome " ) ; System . out . println ( " " ) ; } } } }