Function to check if a singly 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 povar to new Node ; A utility function to prvar a given linked list ; Start with the empty list
class Node { constructor ( val ) { this . data = val ; this . next = null ; } } var head ; var slow_ptr , fast_ptr , second_half ; function isPalindrome ( head ) { slow_ptr = head ; fast_ptr = head ; var prev_of_slow_ptr = head ; var midnode = null ; var 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 ; } function reverse ( ) { var prev = null ; var current = second_half ; var next ; while ( current != null ) { next = current . next ; current . next = prev ; prev = current ; current = next ; } second_half = prev ; } function compareLists ( head1 , head2 ) { var temp1 = head1 ; var 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 ; } function push ( new_data ) { var new_node = new Node ( new_data ) ; new_node . next = head ; head = new_node ; } function printList ( ptr ) { while ( ptr != null ) { document . write ( ptr . data + " " ) ; ptr = ptr . next ; } document . write ( " " ) ; } var str = [ ' ' , ' ' , ' ' , ' ' , ' ' , ' ' , ' ' ] ; var string = str . toString ( ) ; for ( i = 0 ; i < 7 ; i ++ ) { push ( str [ i ] ) ; printList ( head ) ; if ( isPalindrome ( head ) != false ) { document . write ( " " ) ; document . write ( " " ) ; } else { document . write ( " " ) ; document . write ( " " ) ; } }