1. Implement Singly Linked List
2. Convert the Singly Linked List to Doubly Linked List

#include <iostream>

struct Node {
    Node* next;
    int val;

    Node(int val, Node* next)
        :
        val(val),
        next(next)
    {}
};

struct DoublyLinkedListNode {
    DoublyLinkedListNode* next;
    DoublyLinkedListNode* prev;
    int val;

    DoublyLinkedListNode(int val)
        :
        val(val)
    {}
};


DoublyLinkedListNode* copyUtil(Node* root) {
    if(root == nullptr) return nullptr;

    DoublyLinkedListNode* dRoot = new DoublyLinkedListNode(root->val);
    dRoot->next = copyUtil(root->next);
    if(dRoot->next != nullptr) dRoot->next->prev = dRoot;
    return dRoot;
}

DoublyLinkedListNode* copy(Node* root) {
    DoublyLinkedListNode* dRoot = copyUtil(root);
    DoublyLinkedListNode* end = nullptr;
    for(DoublyLinkedListNode* ptr = dRoot; ptr != nullptr; ptr = ptr->next) {
        end = ptr;
    }
    dRoot->prev = end;
    return dRoot;
}

int main() {
    Node* root = new Node(1, new Node(3, new Node(5, nullptr)));

    DoublyLinkedListNode* dRoot = copy(root);

    for(DoublyLinkedListNode* ptr = dRoot; ptr != nullptr; ptr = ptr->next) {
        std::cout << ptr->val << " ";
    }

    std::cout << std::endl;

    DoublyLinkedListNode* ptr1 = dRoot;
    DoublyLinkedListNode* ptr2 = ptr1->next;
    DoublyLinkedListNode* ptr3 = ptr2->next;

    std::cout << ptr1->prev->val << " " << ptr2->prev->val << " " << ptr3->prev->val << " ";

    return 0;
}