Dada una lista enlazada con un bucle, la tarea es encontrar si es palíndromo o no. No se le permite eliminar el bucle.
Ejemplos:
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.
Algoritmo:
A continuación se muestra la implementación.
C++
// C++ program to check if a linked list with // loop is palindrome or not. #include<bits/stdc++.h> 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 << "\nPalindrome" : cout << "\nNot 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>
Producción
Palindrome
Complejidad temporal: O(n)
Espacio auxiliar: O(n)
Este artículo es una contribución de Sahil Chhabra (akku) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA