Initial and untested solution for "copy linked list with random pointer" from https://www.youtube.com/watch?v=Y189fjNEMWU

random_linked_list.c

/* Analysis:
- Storage is O(1)
- Time is O(2*N)

Post-morten after looking up alternate solutions:
* https://www.geeksforgeeks.org/clone-linked-list-next-random-pointer-o1-space/
  - new list is created interleaved with old nodes
  - first pass creates the new nodes and a second pass is used to disconnect the old and new lists
  - next pointers of the original node is clobbered and then restored -- a better solution than mine
  - Time complexity is the same as mine.  Space complexity is slightly better than mine.
*/

#include <inttypes.h>
#include <malloc.h>

/* Assumptions:
    - malloc never fails
    - destroying the original linked list is allowed
*/

typedef struct _RLL {
    union {
        RLL *next;
        RLL *cpy;
    } u1;
    union {
        RLL *random;
        RLL *ori;
    } u2;
    int64_t value;
} RLL;



RLL * rll_deepcopy(RLL *rllHead) {
    /* Destructive deep copy a random linked list.   
     */

    RLL * rllCopyHead = NULL;
    RLL * rllCopyCurr = NULL;
    RLL * rllCopyPrev = NULL;
    RLL * rllCurr;
    RLL * rllNext = NULL;

    if (rllHead == NULL) {
        return NULL;
    }

    /* this loop copies the value and maps between original and new */
    rllCurr = rllHead;
    while (rllCurr != NULL) {
        /* create new node */
        rllCopyCurr = (RLL *)malloc(sizeof(RLL));

        if (rllCurr == rllHead) {
            /* set the head and prev of our new list */
            rllCopyHead = rllCopyCurr;
            rllCopyPrev = rllCopyCurr;
        } else {
            /* update prev's next */
            rllCopyPrev->u1.next = rllCopyCurr;
        }

        /* copy value from original to new */
        rllCopyCurr->value = rllCurr->value;
        /* new node has pointer to original */
        rllCopyCurr->u2.ori = rllCurr;
        /* temp var saves address of the next node */
        rllNext = rllCurr->u1.next;
        /* original has a pointer to new (by clobbering its next pointer) */
        rllCurr->u1.cpy = rllCopyCurr;

        /* move to the next */
        rllCurr = rllNext;
    }

    /* this loop updates the copy list's random */
    rllCopyCurr = rllCopyHead;
    while (rllCopyCurr != NULL) {
        rllCurr = rllCopyCurr->u2.ori;
        rllCopyCurr->u2.random = rllCurr->u2.ori->u1.cpy;
    }
    return rllCopyHead;
}