Check linked list with a loop is palindrome or not | C ++ 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 program to test above function ; Create a loop for testing
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next ; } ; Node * getLoopstart ( Node * loop_node , Node * head ) { Node * ptr1 = loop_node ; Node * ptr2 = loop_node ; unsigned 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 ; } Node * detectAndgetLoopstarting ( Node * head ) { Node * slow_p = head , * fast_p = head , * loop_start ; while ( slow_p && fast_p && fast_p -> next ) { 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 ; } bool isPalindromeUtil ( Node * head , Node * loop_start ) { Node * ptr = head ; stack < int > s ; 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 . top ( ) ) s . pop ( ) ; else return false ; if ( ptr == loop_start ) count = 1 ; ptr = ptr -> next ; } return true ; } bool isPalindrome ( Node * head ) { Node * loop_start = detectAndgetLoopstarting ( head ) ; return isPalindromeUtil ( head , loop_start ) ; } Node * newNode ( int key ) { Node * temp = new Node ; temp -> data = key ; temp -> next = NULL ; return temp ; } int main ( ) { 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 ; isPalindrome ( head ) ? cout << " Palindrome " : cout << " Not Palindrome " return 0 ; }