Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <stack>
- using namespace std;
- struct Node
- {
- int data;
- struct Node *next;
- };
- struct Node *createNode(int val) {
- struct Node *tmp =
- (struct Node*)malloc(sizeof(struct Node));
- tmp->data = val;
- tmp->next = NULL;
- return tmp;
- }
- // Iterative method to check if given
- // linked list is pallindrome or not using stacks.
- bool checkLLPalUsingStack(struct Node *head) {
- stack<struct Node*> stk;
- struct Node *curr = head;
- while(curr) {
- stk.push(curr);
- curr = curr->next;
- }
- curr = head;
- while(curr) {
- if(curr->data != stk.top()->data) {
- return false;
- }
- stk.pop();
- curr = curr->next;
- }
- return true;
- }
- // Recursive approach to check
- // if linked list is pallindrome or not
- bool checkLinkedListPal(struct Node *head, struct Node *next)
- {
- if(next == NULL) return true;
- static struct Node *stHead = head;
- bool res = checkLinkedListPal(stHead,
- next->next) &&
- (stHead->data == next->data);
- stHead = stHead->next;
- return res;
- }
- // Loop over half of the list and check if pallindrome.
- bool checkLinkedListPalHalf(
- struct Node *head,
- struct Node *next,
- struct Node *far)
- {
- static bool isEvenLen = false;
- static struct Node *halfHead = head;
- if(far->next == NULL) {
- isEvenLen = false;
- halfHead = next->next;
- return true;
- }
- if(far->next->next == NULL) {
- isEvenLen = true;
- halfHead = next;
- return true;
- }
- bool res = checkLinkedListPalHalf(
- halfHead,
- next->next,
- far->next->next) &&
- (halfHead->data == next->data);
- halfHead = halfHead->next;
- return res;
- }
- int main(int argc, char* argv[]) {
- struct Node *head = createNode(20);
- head->next = createNode(15);
- head->next->next = createNode(10);
- head->next->next->next =
- createNode(5);
- head->next->next->next->next =
- createNode(10);
- head->next->next->next->next->next =
- createNode(15);
- head->next->next->next->next->next->next =
- createNode(20);
- cout<<"Given LinkedList is Pallindrome: "<<
- (checkLLPalUsingStack(head) ? "True" : "False")
- <<endl;
- cout<<"Given LinkedList is Pallindrome: "<<
- (checkLinkedListPal(head, head) ? "True" : "False")
- <<endl;
- cout<<"Given LinkedList is Pallindrome: "<<
- (checkLinkedListPalHalf(head, head, head) ? "True" : "False")
- <<endl;
- }
- // Output
- /*
- Given LinkedList is Pallindrome: True
- Given LinkedList is Pallindrome: True
- Given LinkedList is Pallindrome: True
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement