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