Reputation: 83
I have got 2 linkedlist, and i want to copy element in both set into newSet, so that i can remove the deplicate value in the newset and display it. So far everything seem to be going wrong, it doesn't copy the set.
struct Node *Union(struct Node *Link1, struct Node *Link2)
{
struct Node * set1 = Link1;
struct Node * set2 = Link2;
//Creat a new set
struct Node * newSet = (struct Node *) malloc(sizeof(struct Node));
while(set1 != NULL && set2 != NULL)
{
//copy sets to newSet
newSet->data = set1->data;
newSet->data = set2->data;
newSet->next = Union(set1->next, set2->next);
}
return (newSet);
}
Any help appriacted
Upvotes: 0
Views: 78
Reputation: 881453
Your main problem is that you allocate a node for the new value then overwrite it with the head of both lists and advance both pointers. That means you'll lose every second node.
In addition, concatenating two lists is not really a good fit for recursion since the search space doesn't reduce that fast (ideal candidates for recursion, like a binary chop or a multi-way tree traversal, throw away a large amount of the search space with each recursion call). You can do it iteratively with something like, (assuming sorted ascending, and using pseudo-code since it's homework):
def union (link1, link2):
set1 = link1, set2 = link2
headnode = NULL, tailnode = NULL
# Continue until both lists empty.
while set1 is not NULL and set2 is not NULL:
# Create new node and set next pointer to NULL.
newnode = alloc_node()
newnode->next = NULL
# Select which set will provide the next node.
if set1 is NULL:
newnode->data = set2->data, set2 = set2->next
else if set2 is NULL:
newnode->data = set1->data, set1 = set1->next
else if set2->data is less than set1->data:
newnode->data = set2->data, set2 = set2->next
else:
newnode->data = set1->data, set1 = set1->next
# Add to end of (possibly empty) list.
if headnode is NULL:
headnode = newnode, tailnode = newnode
else:
tailnode->next = newnode, tailnode = newnode
return headnode
It basically works by doing one iteration per node added to your destination list, until both source lists are empty. If one of the source lists is empty, it selects the next node from the other list.
Otherwise, it selects the next node from the list whose current pointer has the lowest value.
Upvotes: 1