int length(Node *head)
{
    int length = 0;
    while (head != NULL)
        head = head->next, length++;
    return length;
}

node *append_LinkedList(node *head, int n)
{
    if (head == NULL || head->next == NULL) // if only one element is there no need to do anything
        return head;

    int length = 0;

    node *trav = head;

    while (trav->next != NULL) // coz we need the second last node
    {
        trav = trav->next;
        length++;
    }

    length++; // we stopped at the last node

    if (length - n <= 0) // this is assumed to be Okay as per the question
        return head;

    trav->next = head; // connected the last to the head

    // go to the start
    trav = head;

    for (int i = 0; i < length - n - 1; i++)
        trav = trav->next;

    head = trav->next; // the new head, to be returned

    trav->next = NULL;
    return head;
}

node *eliminate_duplicate(node *head)
{
    // sorted list
    if (head == NULL || head->next == NULL)
        return head;

    node *trav = head;

    // step by step elimination, deleting at index 1 from the current.
    // this means we don't have to delete the first node ever, so no need of the special case

    while (trav->next != NULL) // stop when you are the last man standing
    {
        if (trav->data == trav->next->data)
        {
            node *to_be_deleted = trav->next;
            trav->next = trav->next->next;
            delete to_be_deleted; // trav not changed
        }
        else
            trav = trav->next;
    }

    return head;
}

// Iterative Approach

void print_linkedlist_spl(node *head)
{
    if (head == NULL)
        return; // uni loop is a palindrome

    // making a new linked list;

    node *phead = NULL; // we need to point here for the first node

    while (head != NULL)
    {
        node *newnode = new node(head->data); // creates a node with data from the original list
        newnode->next = phead;                // node points to phead
        phead = newnode;                      // phead becomes the node we need to point to in the next iteration

        head = head->next; // traverse the original list by one step
    }

    // head at null, phead at the last node of the original list. Hence it is the head.

    // Now, just travel the list with phead, and deallocate memory for each block.

    node* to_be_deleted = 0;
    while(phead!=NULL)
    {
        to_be_deleted = phead;

        cout << to_be_deleted -> data << " ";
        delete to_be_deleted;

        phead = phead->next;
        to_be_deleted = phead;
    }
}
---------------------
// Recursive Approach

void print_linkedlist_spl(node *head)
{
    if (head == NULL)
        return;
    print_linkedlist_spl(head->next);
    cout << head->data << " ";
}

bool check_palindrome(node *head)
{
    // for doing in o(1) space we need to reverse the list from the middle
    if (head == NULL || head->next == NULL)
        return true;

    node *travx = head, *trav2x = head;

    while (trav2x != NULL && trav2x->next != NULL)
    {
        trav2x = trav2x->next->next;
        travx = travx->next;
    }
    // trav2x reaches the end while travx reaches the first half's last, or the middle

    /* even size = 1 2 3 4 5 6
        pass - (travx, trav2x)
        1 - (1, 2)
        2 - (2, 4)
        3 - (3, 6)

        Conclusion: 1st half of the list
        Proof: PMI
        --------------------

        odd size = 1 2 3 4 5
        pass - (travx, trav2x)
        1 - (1, 2)
        2 - (2, 4)
        stop
        Conclusion: 1st half of the list
        Proof: PMI

        // how to acertain:
        if trav2x == NULL, it is an odd size list. do travx = trav -> next -> next; you are on the 1st of the right side list

        else // (i.e trav->next==NULL)
            trav = trav -> next, you are on the first of the right half
    */

    // reverse the second half of the list, remember p is the element not in the list
    // q, r is the head of the reversed linked list

    node *r = 0, *q = 0, *p = travx;

    while (p != NULL)
    {
        q = p;       // q comes at p
        p = p->next; // p moves over befor the current node loses the next

        q->next = r; // join made
        r = q;       // r moves over
    }

    node *trav = r;
    // both head and trav follow the same distance, so checking any one would suffice

    while (trav != NULL)
    {
        if (trav->data != head->data)
            return false;

        trav = trav->next;
        head = head->next;
    }

    return true;
}