#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.

    a = head;

    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

void reverse(Node* &head)


    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

    head = prev;



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

bool isPalindrome(Node* head)


    // 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


    bHead = 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

    aTail->next = bHead;


    // 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);


    if (isPalindrome(head))

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


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


    return 0;


Source link


Please enter your comment!
Please enter your name here