Monday, October 8, 2012

Make a copy of Linked List

Write a procedure to make a copy of given Linked List.

Below we have both iterative and recursive procedure. But recursive procedure is not good as it requires extra stack space proportional to its length.

/*
 * Node of Linked List
 */
struct node {
       int data;
       struct node* next;
};
typedef struct node* nodeptr;


/*
 * Make a duplicate copy of given linked list(Iterative Procedure)
 */
nodeptr CopyListIterative(nodeptr head)
{
        nodeptr current = head;
        nodeptr newList = NULL;
        nodeptr tail = NULL;
        while(current != NULL) {
                      if(newList == NULL) {
                                 newList = (nodeptr) malloc(sizeof(struct node));
                                 newList->data = current->data;
                                 newList->next = NULL;
                                 tail = newList;
                      } else {
                                 tail->next = (nodeptr) malloc(sizeof(struct node));
                                 tail = tail->next;
                                 tail->data = current->data;
                                 tail->next = NULL;
                      }
                      current = current->next;
        }
        return newList;
}

/*
 * Make a duplicate copy of given linked list(Recursive Procedure)
 */
nodeptr CopyListRecursive(nodeptr head)
{
        if(head == NULL) return NULL;
        else {
             nodeptr current = head;
             nodeptr newList = (nodeptr) malloc(sizeof(struct node));
             newList->data = current->data;
             newList->next = CopyList(current->next);
             return newList;
        }
}

No comments:

Post a Comment