Sprawdź, czy lista połączona z pętlą jest palindromem, czy nie
Biorąc pod uwagę połączoną listę z pętlą, zadaniem jest sprawdzenie, czy jest to palindrom, czy nie. Nie możesz usunąć pętli.
Przykłady:
Input : 1 -> 2 -> 3 -> 2 /| |/ ------- 1 Output: Palindrome Linked list is 1 2 3 2 1 which is a palindrome. Input : 1 -> 2 -> 3 -> 4 /| |/ ------- 1 Output: Not Palindrome Linked list is 1 2 3 4 1 which is a not palindrome.
Algorytm:
- Wykryj pętlę za pomocą algorytmu wykrywania cyklu Floyda.
- Następnie znajdź węzeł początkowy pętli, jak opisano w Ten
- Sprawdź, czy połączona lista jest palindromowa, czy nie, jak omówiono w Ten
Poniżej realizacja.
C++ // C++ program to check if a linked list with // loop is palindrome or not. #include using namespace std ; /* Link list node */ struct Node { int data ; struct Node * next ; }; /* 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 */ Node * getLoopstart ( Node * loop_node Node * head ) { Node * ptr1 = loop_node ; Node * ptr2 = loop_node ; // Count the number of nodes in loop unsigned int k = 1 i ; while ( ptr1 -> next != ptr2 ) { ptr1 = ptr1 -> next ; k ++ ; } // Fix one pointer to head ptr1 = head ; // And the other pointer to k nodes after head ptr2 = head ; for ( i = 0 ; i < k ; i ++ ) ptr2 = ptr2 -> next ; /* Move both pointers at the same pace they will meet at loop starting node */ while ( ptr2 != ptr1 ) { ptr1 = ptr1 -> next ; ptr2 = ptr2 -> next ; } return ptr1 ; } /* This function detects and find loop starting node in the list*/ Node * detectAndgetLoopstarting ( Node * head ) { Node * slow_p = head * fast_p = head * loop_start ; //Start traversing list and detect loop while ( slow_p && fast_p && fast_p -> next ) { slow_p = slow_p -> next ; fast_p = fast_p -> next -> next ; /* If slow_p and fast_p meet then find the loop starting node*/ if ( slow_p == fast_p ) { loop_start = getLoopstart ( slow_p head ); break ; } } // Return starting node of loop return loop_start ; } // Utility function to check if a linked list with loop // is palindrome with given starting point. bool isPalindromeUtil ( Node * head Node * loop_start ) { Node * ptr = head ; stack < int > s ; // Traverse linked list until last node is equal // to loop_start and store the elements till start // in a stack 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 ; // Traverse linked list until last node is // equal to loop_start second time while ( ptr != loop_start || count != 1 ) { // Compare data of node with the top of stack // If equal then continue if ( ptr -> data == s . top ()) s . pop (); // Else return false else return false ; if ( ptr == loop_start ) count = 1 ; ptr = ptr -> next ; } // Return true if linked list is palindrome return true ; } // Function to find if linked list is palindrome or not bool isPalindrome ( Node * head ) { // Find the loop starting node Node * loop_start = detectAndgetLoopstarting ( head ); // Check if linked list is palindrome return isPalindromeUtil ( head loop_start ); } Node * newNode ( int key ) { Node * temp = new Node ; temp -> data = key ; temp -> next = NULL ; return temp ; } /* Driver program to test above function*/ 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 ); /* Create a loop for testing */ head -> next -> next -> next -> next -> next = head -> next -> next ; isPalindrome ( head ) ? cout < < ' n Palindrome' : cout < < ' n Not Palindrome' ; return 0 ; }
Java // Java program to check if a linked list // with loop is palindrome or not. import java.util.* ; class GfG { /* Link list node */ static class Node { int data ; Node next ; } /* 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 */ static Node getLoopstart ( Node loop_node Node head ) { Node ptr1 = loop_node ; Node ptr2 = loop_node ; // Count the number of nodes in loop int k = 1 i ; while ( ptr1 . next != ptr2 ) { ptr1 = ptr1 . next ; k ++ ; } // Fix one pointer to head ptr1 = head ; // And the other pointer to k // nodes after head ptr2 = head ; for ( i = 0 ; i < k ; i ++ ) ptr2 = ptr2 . next ; /* Move both pointers at the same pace they will meet at loop starting node */ while ( ptr2 != ptr1 ) { ptr1 = ptr1 . next ; ptr2 = ptr2 . next ; } return ptr1 ; } /* This function detects and find loop starting node in the list*/ static Node detectAndgetLoopstarting ( Node head ) { Node slow_p = head fast_p = head loop_start = null ; //Start traversing list and detect loop 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 and fast_p meet then find the loop starting node*/ if ( slow_p == fast_p ) { loop_start = getLoopstart ( slow_p head ); break ; } } // Return starting node of loop return loop_start ; } // Utility function to check if // a linked list with loop is // palindrome with given starting point. static boolean isPalindromeUtil ( Node head Node loop_start ) { Node ptr = head ; Stack < Integer > s = new Stack < Integer > (); // Traverse linked list until last node // is equal to loop_start and store the // elements till start in a stack 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 ; // Traverse linked list until last node is // equal to loop_start second time while ( ptr != loop_start || count != 1 ) { // Compare data of node with the top of stack // If equal then continue if ( ptr . data == s . peek ()) s . pop (); // Else return false else return false ; if ( ptr == loop_start ) count = 1 ; ptr = ptr . next ; } // Return true if linked list is palindrome return true ; } // Function to find if linked list // is palindrome or not static boolean isPalindrome ( Node head ) { // Find the loop starting node Node loop_start = detectAndgetLoopstarting ( head ); // Check if linked list is palindrome return isPalindromeUtil ( head loop_start ); } static Node newNode ( int key ) { Node temp = new Node (); temp . data = key ; temp . next = null ; return temp ; } /* Driver code*/ 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 ); /* Create a loop for testing */ head . next . next . next . next . next = head . next . next ; if ( isPalindrome ( head ) == true ) System . out . println ( 'Palindrome' ); else System . out . println ( 'Not Palindrome' ); } } // This code is contributed by prerna saini
Python # Python3 program to check if a linked list # with loop is palindrome or not. # Node class class Node : # Constructor to initialize the node object def __init__ ( self data ): self . data = data self . next = None # 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 def getLoopstart ( loop_node head ): ptr1 = loop_node ptr2 = loop_node # Count the number of nodes in loop k = 1 i = 0 while ( ptr1 . next != ptr2 ): ptr1 = ptr1 . next k = k + 1 # Fix one pointer to head ptr1 = head # And the other pointer to k # nodes after head ptr2 = head i = 0 while ( i < k ) : ptr2 = ptr2 . next i = i + 1 # Move both pointers at the same pace #they will meet at loop starting node */ while ( ptr2 != ptr1 ): ptr1 = ptr1 . next ptr2 = ptr2 . next return ptr1 # This function detects and find # loop starting node in the list def detectAndgetLoopstarting ( head ): slow_p = head fast_p = head loop_start = None # Start traversing list and detect loop while ( slow_p != None and fast_p != None and fast_p . next != None ) : slow_p = slow_p . next fast_p = fast_p . next . next # If slow_p and fast_p meet then find # the loop starting node if ( slow_p == fast_p ) : loop_start = getLoopstart ( slow_p head ) break # Return starting node of loop return loop_start # Utility function to check if # a linked list with loop is # palindrome with given starting point. def isPalindromeUtil ( head loop_start ): ptr = head s = [] # Traverse linked list until last node # is equal to loop_start and store the # elements till start in a stack count = 0 while ( ptr != loop_start or count != 1 ): s . append ( ptr . data ) if ( ptr == loop_start ) : count = 1 ptr = ptr . next ptr = head count = 0 # Traverse linked list until last node is # equal to loop_start second time while ( ptr != loop_start or count != 1 ): # Compare data of node with the top of stack # If equal then continue if ( ptr . data == s [ - 1 ]): s . pop () # Else return False else : return False if ( ptr == loop_start ) : count = 1 ptr = ptr . next # Return True if linked list is palindrome return True # Function to find if linked list # is palindrome or not def isPalindrome ( head ) : # Find the loop starting node loop_start = detectAndgetLoopstarting ( head ) # Check if linked list is palindrome return isPalindromeUtil ( head loop_start ) def newNode ( key ) : temp = Node ( 0 ) temp . data = key temp . next = None return temp # Driver code 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 ) # Create a loop for testing head . next . next . next . next . next = head . next . next if ( isPalindrome ( head ) == True ): print ( 'Palindrome' ) else : print ( 'Not Palindrome' ) # This code is contributed by Arnab Kundu
C# // C# program to check if a linked list // with loop is palindrome or not. using System ; using System.Collections.Generic ; class GfG { /* Link list node */ class Node { public int data ; public Node next ; } /* 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 */ static Node getLoopstart ( Node loop_node Node head ) { Node ptr1 = loop_node ; Node ptr2 = loop_node ; // Count the number of nodes in loop int k = 1 i ; while ( ptr1 . next != ptr2 ) { ptr1 = ptr1 . next ; k ++ ; } // Fix one pointer to head ptr1 = head ; // And the other pointer to k // nodes after head ptr2 = head ; for ( i = 0 ; i < k ; i ++ ) ptr2 = ptr2 . next ; /* Move both pointers at the same pace they will meet at loop starting node */ while ( ptr2 != ptr1 ) { ptr1 = ptr1 . next ; ptr2 = ptr2 . next ; } return ptr1 ; } /* This function detects and find loop starting node in the list*/ static Node detectAndgetLoopstarting ( Node head ) { Node slow_p = head fast_p = head loop_start = null ; //Start traversing list and detect loop 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 and fast_p meet then find the loop starting node*/ if ( slow_p == fast_p ) { loop_start = getLoopstart ( slow_p head ); break ; } } // Return starting node of loop return loop_start ; } // Utility function to check if // a linked list with loop is // palindrome with given starting point. static bool isPalindromeUtil ( Node head Node loop_start ) { Node ptr = head ; Stack < int > s = new Stack < int > (); // Traverse linked list until last node // is equal to loop_start and store the // elements till start in a stack 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 ; // Traverse linked list until last node is // equal to loop_start second time while ( ptr != loop_start || count != 1 ) { // Compare data of node with the top of stack // If equal then continue if ( ptr . data == s . Peek ()) s . Pop (); // Else return false else return false ; if ( ptr == loop_start ) count = 1 ; ptr = ptr . next ; } // Return true if linked list is palindrome return true ; } // Function to find if linked list // is palindrome or not static bool isPalindrome ( Node head ) { // Find the loop starting node Node loop_start = detectAndgetLoopstarting ( head ); // Check if linked list is palindrome return isPalindromeUtil ( head loop_start ); } static Node newNode ( int key ) { Node temp = new Node (); temp . data = key ; temp . next = null ; return temp ; } /* Driver code*/ 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 ); /* Create a loop for testing */ head . next . next . next . next . next = head . next . next ; if ( isPalindrome ( head ) == true ) Console . WriteLine ( 'Palindrome' ); else Console . WriteLine ( 'Not Palindrome' ); } } /* This code is contributed by 29AjayKumar */
JavaScript < script > // javascript program to check if a linked list // with loop is palindrome or not.class GfG { /* Link list node */ class Node { constructor () { this . data = 0 ; this . next = null ; } } /* * 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 */ function getLoopstart ( loop_node head ) { var ptr1 = loop_node ; var ptr2 = loop_node ; // Count the number of nodes in loop var k = 1 i ; while ( ptr1 . next != ptr2 ) { ptr1 = ptr1 . next ; k ++ ; } // Fix one pointer to head ptr1 = head ; // And the other pointer to k // nodes after head ptr2 = head ; for ( i = 0 ; i < k ; i ++ ) ptr2 = ptr2 . next ; /* * Move both pointers at the same pace they will meet at loop starting node */ while ( ptr2 != ptr1 ) { ptr1 = ptr1 . next ; ptr2 = ptr2 . next ; } return ptr1 ; } /* * This function detects and find loop starting node in the list */ function detectAndgetLoopstarting ( head ) { var slow_p = head fast_p = head loop_start = null ; // Start traversing list and detect loop 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 and fast_p meet then find the loop starting node */ if ( slow_p == fast_p ) { loop_start = getLoopstart ( slow_p head ); break ; } } // Return starting node of loop return loop_start ; } // Utility function to check if // a linked list with loop is // palindrome with given starting point. function isPalindromeUtil ( head loop_start ) { var ptr = head ; var s = []; // Traverse linked list until last node // is equal to loop_start and store the // elements till start in a stack var 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 ; // Traverse linked list until last node is // equal to loop_start second time while ( ptr != loop_start || count != 1 ) { // Compare data of node with the top of stack // If equal then continue var stk = s . pop (); if ( ptr . data == stk ); // Else return false else { s . push ( stk ); return false ; } if ( ptr == loop_start ) count = 1 ; ptr = ptr . next ; } // Return true if linked list is palindrome return true ; } // Function to find if linked list // is palindrome or not function isPalindrome ( head ) { // Find the loop starting node var loop_start = detectAndgetLoopstarting ( head ); // Check if linked list is palindrome return isPalindromeUtil ( head loop_start ); } function newNode ( key ) { var temp = new Node (); temp . data = key ; temp . next = null ; return temp ; } /* Driver code */ var 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 ); /* Create a loop for testing */ head . next . next . next . next . next = head . next . next ; if ( isPalindrome ( head ) == true ) document . write ( 'Palindrome' ); else document . write ( 'Not Palindrome' ); // This code contributed by aashish1995 < /script>
Wyjście
Palindrome
Złożoność czasowa: O(n)
Przestrzeń pomocnicza: O(n)
Utwórz quiz
