Check linked list with a loop is palindrome or not | Java program to check if a linked list with loop is palindrome or not . ; Link list node ; Function to find loop starting node . loop_node -- > Pointer to one of the loop nodes head -- > Pointer to the start node of the linked list ; Count the number of nodes in loop ; Fix one pointer to head ; And the other pointer to k nodes after head ; Move both pointers at the same pace , they will meet at loop starting node ; This function detects and find loop starting node in the list ; Start traversing list and detect loop ; If slow_p and fast_p meet then find the loop starting node ; Return starting node of loop ; Utility function to check if a linked list with loop is palindrome with given starting point . ; Traverse linked list until last node is equal to loop_start and store the elements till start in a stack ; Traverse linked list until last node is equal to loop_start second time ; Compare data of node with the top of stack If equal then continue ; Else return false ; Return true if linked list is palindrome ; Function to find if linked list is palindrome or not ; Find the loop starting node ; Check if linked list is palindrome ; Driver code ; Create a loop for testing
import java . util . * ; class GfG { static class Node { int data ; Node next ; } static Node getLoopstart ( Node loop_node , Node head ) { Node ptr1 = loop_node ; Node ptr2 = loop_node ; int k = 1 , i ; while ( ptr1 . next != ptr2 ) { ptr1 = ptr1 . next ; k ++ ; } ptr1 = head ; ptr2 = head ; for ( i = 0 ; i < k ; i ++ ) ptr2 = ptr2 . next ; while ( ptr2 != ptr1 ) { ptr1 = ptr1 . next ; ptr2 = ptr2 . next ; } return ptr1 ; } static Node detectAndgetLoopstarting ( Node head ) { Node slow_p = head , fast_p = head , loop_start = null ; while ( slow_p != null && fast_p != null && fast_p . next != null ) { slow_p = slow_p . next ; fast_p = fast_p . next . next ; if ( slow_p == fast_p ) { loop_start = getLoopstart ( slow_p , head ) ; break ; } } return loop_start ; } static boolean isPalindromeUtil ( Node head , Node loop_start ) { Node ptr = head ; Stack < Integer > s = new Stack < Integer > ( ) ; int count = 0 ; while ( ptr != loop_start count != 1 ) { s . push ( ptr . data ) ; if ( ptr == loop_start ) count = 1 ; ptr = ptr . next ; } ptr = head ; count = 0 ; while ( ptr != loop_start count != 1 ) { if ( ptr . data == s . peek ( ) ) s . pop ( ) ; else return false ; if ( ptr == loop_start ) count = 1 ; ptr = ptr . next ; } return true ; } static boolean isPalindrome ( Node head ) { Node loop_start = detectAndgetLoopstarting ( head ) ; return isPalindromeUtil ( head , loop_start ) ; } static Node newNode ( int key ) { Node temp = new Node ( ) ; temp . data = key ; temp . next = null ; return temp ; } public static void main ( String [ ] args ) { Node head = newNode ( 50 ) ; head . next = newNode ( 20 ) ; head . next . next = newNode ( 15 ) ; head . next . next . next = newNode ( 20 ) ; head . next . next . next . next = newNode ( 50 ) ; head . next . next . next . next . next = head . next . next ; if ( isPalindrome ( head ) == true ) System . out . println ( " Palindrome " ) ; else System . out . println ( " Not ▁ Palindrome " ) ; } }