Duplicating Link List with Random Pointers

Recently I came across a very interesting question on Link Lists. I tried a lot of crap before i got a click and I solved the problem. The problem can be stated as follows

We are given a singly-linked list A. The nodes of A consists of usual data and next pointer. Along with these there is another pointer random which points to a random node of A. We are supposed to make a new linked list B which is copy of A as far as the structure is concerned but all its nodes are newly allocated. Develop an algorithm such that its time complexity is O(n).

Following is my solution coded in C. I thoroughly enjoyed solving the problem and urge everyone to try to solve it yourself. You will surely get to the solution.

/*

 * duplicate_link_list.c

*

* duplicates a given link list where each node has a next pointer

* and a random pointer pointing to any node in the link list

*

 */

#include <assert.h>

#include <malloc.h>

#include <stdlib.h>

#include <stdio.h>

typedef struct _node Node;

struct _node {

    int  data;

    Node *next;

    Node *random;

};

/*

 * duplicates link list given as src and put the duplicate into

 * *dst

 *

 * assumes the link list are having sentinal elements

 *

 */

void duplicate(Node *src, Node **dst) {

    Node *i_s, *i_d, *t;

    assert(*dst != NULL);

    /* FIRST PASS Allocate new nodes */

    i_s = src;

    i_d = *dst;

    i_s = i_s->next;

    while(i_s)

    {

        t = (Node *)malloc(sizeof(Node) * 1);

        assert(t != NULL);
        t->data     = i_s->data;
        t->next     = i_s->random;
        t->random   = NULL;
        i_s->random = t;
        i_s = i_s->next;
    }
    /* SECOND PASS: Adjust all new nodes to have there
    *              correct random pointers
*/
    i_s = src->next;
    while(i_s)
    {
        Node *n;
        n = i_s->random;
        n->random = (n->next)->random;
        i_s = i_s->next;
    }
    /* THIRD PASS: Unzip the teo link lists */
    i_s = src->next;
    i_d = *dst;
    while(i_s)
    {
        t           = i_s->random;
        i_s->random = t->next;
        t->next     = NULL;
        i_d->next   = t;
        i_d         = t;
        i_s         = i_s->next;
    }
}