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.
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 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 codeint 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 << "Palindrome" : cout << " Not Palindrome"; return 0;} |
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 stack
Approach 2: Constant Space.
Here’s the approach to check if a linked list is palindrome or not without using extra space:
- Find the middle node of the linked list using the slow and fast pointer approach.
- Reverse the second half of the linked list.
- Traverse both halves of the linked list (first half from start to middle, and second half from middle to end) and compare their data.
- If all the data is same, then the linked list is palindrome. Otherwise, it’s not palindrome.
Here’s the C++ code implementing the above approach:
C++
#include<bits/stdc++.h>using namespace std;// Link list node struct Node{ int data; struct Node * next;};/* Function to reverse a linked list from the given node */Node* reverseList(Node *head){ Node *prev = NULL; Node *curr = head; Node *next; while(curr != NULL) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev;}// Function to check if a linked list is palindrome or notbool isPalindrome(Node* head){ // Find the middle node of the linked list Node *slow = head, *fast = head; while(fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } // Reverse the second half of the linked list Node *rev_second_half = reverseList(slow); // Traverse both halves of the linked list and compare their data Node *p1 = head, *p2 = rev_second_half; while(p2 != NULL) { if(p1->data != p2->data) return false; p1 = p1->next; p2 = p2->next; } return true;}// Utility function to create a new nodeNode *newNode(int key){ Node *temp = new Node; temp->data = key; temp->next = NULL; return temp;}// Driver codeint main(){ Node *head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(2); head->next->next->next->next = newNode(1); isPalindrome(head)? cout<<"Palindrome": cout<<"Not Palindrome"; return 0;} |
Output
Palindrome
Time Complexity: O(n) where n is no of nodes in the linked list
Auxiliary Space: O(1) Uses no extra space.
Please refer complete article on Check linked list with a loop is palindrome or not for more details!
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!
Share your thoughts in the comments
