#include <iostream>

using namespace std;

// Structure to store a node

struct Node {

int data;

Node* next;

// Constructor

Node(int i)

{

this->data = i;

this->next = nullptr;

}

};

// Function to split nodes of the given linked list into two halves using the

// fast/slow pointer strategy. It returns pointer to the tail of first half

Node* FrontBackSplit(Node* head, Node* &a, Node* &b)

{

Node* slow = head;

Node* fast = head->next;

// ‘fast’ by two nodes, and ‘slow’ by single node

while (fast)

{

fast = fast->next;

if (fast)

{

slow = slow->next;

fast = fast->next;

}

}

// ‘slow’ is before the midpoint in the list, so split it in two

// at that point.

b = slow->next;

slow->next = nullptr;

return slow;

}

// Reverses the given linked list by changing its .next pointers and

// its head pointer. Takes a pointer (reference) to the head pointer

{

Node* prev = nullptr;        // the prev pointer

Node* current = head;        // the main pointer

// traverse the list

while (current)

{

// tricky: note the next node

Node* next = current->next;

current->next = prev;  // fix the current node

// advance the two pointers

prev = current;

current = next;

}

// fix the head pointer to point to the new front

}

// Function to if a given linked list is a or not

{

// if length is less than 2, handle separately

if (head == nullptr || head->next == nullptr)

return true;

Node *a, *b, *aTail, *bHead;

// split the linked list into two halves

// If number of nodes are odd, the extra node will go in the first list

aTail = FrontBackSplit(head, a, b);

// reverse second half

reverse(b);

// traverse both lists simultaneously and compare their data

while (a && b)

{

// return false at first data mismatch

if (a->data != b->data)

return false;

// advance both lists to the next nodes

a = a->next;

b = b->next;

}

// restore second half

// restore original linked list before returning by

// linking the first half with the second half

// we reach here only when the linked list is a palindrome

return true;

}

// main function

int main()

{

Node* head = new Node(1);

head->next = new Node(2);

head->next->next = new Node(3);

head->next->next->next = new Node(2);

head->next->next->next->next = new Node(1);

cout << “Linked List is a palindrome.”;

else

cout << “Linked List is not a palindrome.”;

return 0;

}

SHARE