user1285872
user1285872

Reputation: 83

How do I copy elements in 2 linkedlist into an new linkedlist

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

Answers (1)

paxdiablo
paxdiablo

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

Related Questions