Given a linked list with a loop, the task is to find whether it is palindrome or not. You are not allowed to remove the loop.
Examples:
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.
Algorithm:
Below is the implementation.
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 nodeshead --> 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 notbool 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 listdef 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 listdef 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 codehead = 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.nextif(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> |
Output
Palindrome
Time Complexity: O(n)
Auxiliary Space: O(n)
This article is contributed by Sahil Chhabra (akku). If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
