GFG PTOD | 23 Jan | Clone List with Next and Random

Node *cloneLinkedList(Node *head) {
        // Write your code here
        if(head == NULL) return head;
        Node *cur = head;
        // Step 1: create new node and make a link from first to create map
        while(cur) {
            Node *newNode = new Node(cur->data);
            newNode->next = cur->next;
            cur->next = newNode;
            cur = newNode->next;
        }
        // Step 2: Assign random pointer to head2
        cur = head;
        Node *head2 = cur->next;
        while(cur!=NULL) {
            if(cur->random == NULL) cur->next->random = NULL;
            else cur->next->random = cur->random->next;
            cur = cur->next->next;
        }
        //Step 3: Make proper link of head and head2 and return head2
        cur=head;
        while(cur) {
            Node *tmp = cur->next;
            cur->next = tmp->next;
            if(tmp->next) tmp->next = tmp->next->next;
            cur=cur->next;
        }
        return head2;
    }