Get the Union Set in Single Link List

hello everyone, i have a problem in blew program,i dont know how to get the union set without changing the head1. i want to put the union set in the head3.

Code:

/************************************************************************/
/*                Get the Union Set in Single Link List                 */
/************************************************************************/

#include <stdio.h>
#include <stdlib.h>

typedef struct _tagLinkNode
{
    int data;
    struct _tagLinkNode *next;
}LinkNode;


LinkNode* CreateList(LinkNode *head)
{
    head = (LinkNode *)malloc(sizeof(LinkNode));
    if (NULL == head)
    {
        printf("malloc error\n");
        return;
    }
	head->data = 0;
	head->next = NULL;

	return head;
}

void InputData(LinkNode *head)
{
    LinkNode *p = NULL;
    LinkNode *pNode = NULL;
    int data = 0;

    p = head;

    scanf("%d", &data);

    while(-1 != data)
    {
        pNode = (LinkNode *)malloc(sizeof(LinkNode));
        if (NULL == pNode)
        {
            printf("malloc error\n");
            return;
        }
        if (-1 != data)
        {
            pNode->data = data;
            pNode->next = NULL;
            p->next = pNode;
            p = pNode;
        }
        scanf("%d", &data);
    }
}

void OutPutData(LinkNode *pHead)
{
    LinkNode *p = pHead;

    if (NULL != p)
    {
        p = p->next;
    }

    while (NULL != p)
    {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

LinkNode** GetUnion(LinkNode *head1, LinkNode *head2, LinkNode **head3)
{
    LinkNode *p1 = head1;
    LinkNode *p2 = head2;
    LinkNode *p3 = NULL;
    LinkNode *p3pre = NULL;

    if (NULL == p1 && NULL == p2)
    {
        return;
    }

	head3 = (LinkNode **)malloc(sizeof(LinkNode));
	*head3 = (LinkNode *)malloc(sizeof(LinkNode));
	
	if (NULL == *head3 || NULL == head3)
	{
		printf("malloc error\n");
		return NULL;
	}

	(*head3)->data = 0;
	(*head3)->next = NULL;

    p1 = p1->next;
    p2 = p2->next;
    p3 = *head3 = head1;
    p3 = p3->next;

    while (NULL != p2)
    {
        p3pre = *head3;
        p3 = p3pre->next;
        while (NULL != p3)
        {
            if (p2->data == p3->data)
            {
                break;
            }
            p3pre = p3pre->next;
            p3 = p3->next;
        }
        if (NULL == p3)
        {
            p3pre->next = p2;
            p3pre = p3pre->next;
        }
        p2 = p2->next;
	}
	return head3;
}

int main()
{
    LinkNode *list1 = NULL;
    LinkNode *list2 = NULL;
    LinkNode **list3 = NULL;

    list1 = CreateList(list1);
    printf("please input single link list1(-1 end): ");
    InputData(list1);

	  list2 = CreateList(list2);
    printf("please input single link list2(-1 end): ");
    InputData(list2);

    printf("\n\nThe Set 1: ");
    OutPutData(list1);
    printf("The Set2: ");
    OutPutData(list2);

    //list3 = CreateList(list3);

    printf("The Union Set is :");
    list3 = GetUnion(list1, list2, list3);
    OutPutData(*list3);

    return 0;
}

If you can't solve a problem, divide it into smaller problems, try to first write a function to copy() a list and a function to concatenate() two existing lists without creating a new one.
Your getunion function will simply be a composition of those two functions.
You're talking about sets, if this last function must return a set then write a set() function that remove duplicated elements in a list.
Compose everything and you're done.

Get rid of line 87.
If the first thing you do with something that was passed in is to overwrite its value, then there wasn't any point in passing it in.

maybe i didn't express clearly, i mean, i want to use two single link list to get their union set. The "GetUnion" function has logical error but i dont know how to fix it.

Originally Posted by ampc

i want to use two single link list to get their union set.

Well, if by "set" you mean that there are no duplicates, I would ask: are the two linked lists sorted and without duplicates? If so, then this is just a matter of merging them, discarding duplicates as you do so. If not, you can either sort them then merge, or simply join the two linked lists, then sort and remove duplicates.

i mean list 1: 1 2 3 4, list 2: 3 4 5 6, then the union set is 1 2 3 4 5 6

Originally Posted by ampc

i mean list 1: 1 2 3 4, list 2: 3 4 5 6, then the union set is 1 2 3 4 5 6

I would rather you have answered my questions explicitly, but anyway, I assume that your linked lists are sorted and without duplicates. Hence, just merge them. This involves comparing the current nodes of each linked list. The one that is "less than" the other is appended to the new linked list. If both nodes have equal value, you append one and skip the other.

Is there a reason that list3 was declared in main() with multiple indirection?

It seems to me that you should be declaring it as "LinkNode *list3 = NULL;" and passing &list3 into getunion() -> That way you are passing by reference and not value.

Other than that, it should be straight forward: If element is not already in head3, add it to the end.

<edit>
[edit]
Oh, and you'll want to do get rid of line 87
[/edit]

i've improved the GetUnion function.

Code:

LinkNode* GetUnion(LinkNode *head1, LinkNode *head2, LinkNode *head3)
{
    LinkNode *p1 = NULL;
    LinkNode *p2 = NULL;
    LinkNode *p3 = NULL;

    if (NULL != head1 && NULL != head2)
    {
		p3 = head3 = head1;
        p1 = head1->next;
		p2 = head2->next;
		p3 = p1;

		while (NULL != p1 && NULL != p2)
		{
			if (p2->data != p1->data)
			{
				if (NULL != p1->next)
				{
					p1 = p1->next;
				}
				else
				{
					p1->next = p2;
					p3 = p2;
					p1 = head1->next;
					p2 = p2->next;
					p3->next = NULL;
				}
			}
			else
			{
				p2 = p2->next;
				if (NULL != p2 && NULL == p3->next)
				{
					p3->next = p2;
				}
			}
		}
    }
	return head3;
}

may i still improve it?

Hmm... did you test your code with various possible input linked lists? The algorithm I had in mind goes something like this:

Code:

LinkNode* GetUnion(LinkNode *head1, LinkNode *head2)
{
    LinkNode *union_head = NULL;
    LinkNode *union_tail = NULL;

    if ((head1 && head2 && head1->data < head2->data) || (head1 && !head2))
    {
        /* set union head and tail to head1; set head1 to its next node */
    }
    else if (head2)
    {
        /* set union head and tail to head2; set head2 to its next node */
    }

    while (head1 && head2)
    {
        if (head1->data < head2->data)
        {
            /* set union tail's next node to head1;
               set union tail to its next node;
               set head1 to its next node */
        }
        else
        {
            /* set union tail's next node to head2, etc*/
        }
    }

    while (head1)
    {
        /* set union tail's next node to head1, etc */
    }

    while (head2)
    {
        /* set union tail's next node to head2, etc */
    }

    return union_head;
}

Originally Posted by ampc

Code:

				if (NULL != p1->next)

You're using Yoda Conditions... Please don't.

im afraid of missing a '=' in the middle of if

Eh, by the way, in my post #10, the latter two while loops just need to be if statements instead, i.e.,

Code:

if (head1)
{
    /* set union tail's next node to head1 */
}
else if (head2)
{
    /* set union tail's next node to head2 */
}

Originally Posted by ampc

im afraid of missing a '=' in the middle of if

That's what compiler warnings are for.

Besides, it's only as much effort to remember to use == as it is to remember to write it backwards, so you gain nothing.

Originally Posted by iMalc

You're using Yoda Conditions... Please don't.

Before I read that page, I half-expected Yoda Conditions to look like this:

Code:

if (DO || !DO) {
    // there is no try
}

Or like this:

Code:

if (x == 0) {
} else if (x != 0) {
}

By the way, I've recently seen the following if...else if pattern in production code at work:

Code:

if (0 == x) {
    // do something
} else if (0 != x) {
    // do something else
}

It's a double Yoda! The Force must be strong in this code.