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(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