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:
- Detect the loop using the Floyd Cycle Detection Algorithm.
- Then find the starting node of the loop as discussed in this.
- Check the linked list is palindrome or not as discussed in this.
Below is the implementation.
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 is contributed by aashish1995 </script> |
Output:
Palindrome
Time Complexity: O(n) where n is no of nodes in the linked list
Auxiliary Space: O(n) where n is size of List
Please refer complete article on Check linked list with a loop is palindrome or not for more details!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!