Norway


#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

    reverse(b);

    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

    reverse(bHead);

 

    // 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.”;

    else

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

 

    return 0;

}



Source link

LEAVE A REPLY

Please enter your comment!
Please enter your name here