task-8.cpp

#include <iostream>
#include <unordered_map>
#include <stack>
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node(int val) { data = val; next = nullptr; }
};

class SinglyLinkedList {
private:
    Node* head;
public:
    SinglyLinkedList() { head = nullptr; }

    Node* getHead() { return head; }
    void setHead(Node* h) { head = h; }

    void insertAtTail(int val) {
        Node* newNode = new Node(val);
        if (!head) { head = newNode; return; }
        Node* temp = head;
        while (temp->next) temp = temp->next;
        temp->next = newNode;
    }

    void display() {
        Node* temp = head;
        while (temp) { cout << temp->data << " -> "; temp = temp->next; }
        cout << "NULL\n";
    }

    bool isPalindrome() {
        if (!head || !head->next) return true;
        stack<int> s;
        Node* temp = head;
        while (temp) { s.push(temp->data); temp = temp->next; }
        temp = head;
        while (temp) { if (temp->data != s.top()) return false; s.pop(); temp = temp->next; }
        return true;
    }

    void rotate(int k) {
        if (!head || k == 0) return;
        Node* temp = head;
        int len = 1;
        while (temp->next) { temp = temp->next; len++; }
        k = k % len;
        if (k == 0) return;
        temp->next = head;
        Node* newTail = head;
        for (int i = 0; i < len - k - 1; i++) newTail = newTail->next;
        head = newTail->next;
        newTail->next = nullptr;
    }
};

class RandomNode {
public:
    int val;
    RandomNode* next;
    RandomNode* random;
    RandomNode(int x) { val = x; next = nullptr; random = nullptr; }
};

RandomNode* copyRandomList(RandomNode* head) {
    if (!head) return nullptr;
    unordered_map<RandomNode*, RandomNode*> m;
    RandomNode* temp = head;
    while (temp) { m[temp] = new RandomNode(temp->val); temp = temp->next; }
    temp = head;
    while (temp) {
        m[temp]->next = temp->next ? m[temp->next] : nullptr;
        m[temp]->random = temp->random ? m[temp->random] : nullptr;
        temp = temp->next;
    }
    return m[head];
}

int main() {
    SinglyLinkedList list;
    list.insertAtTail(1);
    list.insertAtTail(2);
    list.insertAtTail(3);
    list.insertAtTail(2);
    list.insertAtTail(1);

    cout << "Original List: ";
    list.display();
    cout << "Is Palindrome? " << (list.isPalindrome() ? "YES" : "NO") << endl;

    list.rotate(2);
    cout << "After rotating by 2: ";
    list.display();

    RandomNode* r1 = new RandomNode(1);
    RandomNode* r2 = new RandomNode(2);
    RandomNode* r3 = new RandomNode(3);
    r1->next = r2; r2->next = r3;
    r1->random = r3; r2->random = r1; r3->random = r2;

    RandomNode* copied = copyRandomList(r1);
    RandomNode* temp = copied;
    cout << "Copied Random List: ";
    while (temp) { 
        cout << temp->val << "(R:";
        cout << (temp->random ? temp->random->val : -1) << ") -> "; 
        temp = temp->next; 
    }
    cout << "NULL\n";

    return 0;
}