So I'm doing this assignment and as part of the rules, anything extra defined in helpers needs to be free'd at the end. the question is: take a destination empty linked list, take 2 already sorted linked lists, and merge these two into the destination linked list with their already existing addresses, I'm not allowed to define new nodes. this is what I have
void llmrg(struct llist *dest, struct llist *src1, struct llist *src2)
{
struct llnode *tempdest = dest->front;
struct llnode *tempsrc;
while (src1->front != NULL || src2->front != NULL)
{
if (src2->front == NULL)
{
tempdest->next = src1->front;
src1->front = NULL;
}
else if (src1->front == NULL)
{
tempdest->next = src2->front;
src2->front = NULL;
}
else
{
if ((src2->front == NULL) || (src1->front->item < src2->front->item))
{
tempsrc = src1->front->next;
if (dest->front != NULL)
{
tempdest->next = src1->front;
tempdest = tempdest->next;
}
else
{
dest->front = src1->front;
tempdest = dest->front;
}
src1->front->next = NULL;
src1->front = tempsrc;
}
else
{
tempsrc = src2->front->next;
if (dest->front != NULL)
{
tempdest->next = src2->front;
tempdest = tempdest->next;
}
else
{
dest->front = src2->front;
tempdest = dest->front;
}
src2->front->next = NULL;
src2->front = tempsrc;
}
}
}
free(tempsrc);
free(tempdest);
}
So now my issue is if I don't do the 'free' statements, everything works, but I'm not allowed to do that, but if I free 'tempdest' (free'ing 'tempsrc' doesn't cause an issue), then 1 of the values goes away because it's still stored using tempdest.
So if my lists are (1,3,5) and (2,4,6), result should be (1,2,3,4,5,6), and it works without free'ing, but with free'ing I get (1,2,3,4,0,6).
Also the data structures are:
struct llnode { int item; struct llnode *next; };
struct llist { struct llnode *front; };
By freeing, I don't mean the linked lists, those are obviously being used. I mean the 2 pointers, tempdest and tempsrc, that I created for the sake of solving this question — those need to be freed.
Can someone please help me somehow free tempdest and also keep the value 5?
As I noted in the comments,
Why do you need to free anything? When you merge the two lists, each item in each of the lists should be in the result list, so none of the items should be freed.
Since you have a 'list head' structure (struct llist), you have to set the two old list head structures passed into llmrg() so they don't point to anything any more.
You're not 'allowed' to free either
tempsrcortempdestbecause they are not allocated by your code. They are merely temporary pointers to items in the list. If you free either of them, you will break things. Please getvalgrindif at all possible and use it. It will help you see the error of your ways. By the end of the merge function, you need to ensure thatsrc1->frontis a null pointer, and thatsrc2->frontis a null pointer. But that's all. There's still nothing to free.
This is your code adapted into a test harness. Note that there is no call to malloc() anywhere in this code, and hence no need to call free() anywhere either. This is mainly to make the point rather than because you would use non-dynamic memory allocation in genuine code (but you didn't show the list creation code, and doing things this way avoids having to write that, too).
#include <stdio.h>
struct llnode { int item; struct llnode *next; };
struct llist { struct llnode *front; };
static
void llmrg(struct llist *dest, struct llist *src1, struct llist *src2)
{
struct llnode *tempdest = dest->front;
struct llnode *tempsrc;
while (src1->front != NULL || src2->front != NULL)
{
if (src2->front == NULL)
{
tempdest->next = src1->front;
src1->front = NULL;
}
else if (src1->front == NULL)
{
tempdest->next = src2->front;
src2->front = NULL;
}
else
{
if ((src2->front == NULL) || (src1->front->item < src2->front->item))
{
tempsrc = src1->front->next;
if (dest->front != NULL)
{
tempdest->next = src1->front;
tempdest = tempdest->next;
}
else
{
dest->front = src1->front;
tempdest = dest->front;
}
src1->front->next = NULL;
src1->front = tempsrc;
}
else
{
tempsrc = src2->front->next;
if (dest->front != NULL)
{
tempdest->next = src2->front;
tempdest = tempdest->next;
}
else
{
dest->front = src2->front;
tempdest = dest->front;
}
src2->front->next = NULL;
src2->front = tempsrc;
}
}
}
src1->front = NULL;
src2->front = NULL;
}
static void print_llist(const char *tag, struct llist *list)
{
printf("%s:", tag);
struct llnode *node = list->front;
while (node != 0)
{
printf(" %d", node->item);
node = node->next;
}
putchar('\n');
}
int main(void)
{
struct llnode data[] =
{
{ 1, &data[1] }, { 3, &data[2] }, { 5, 0 },
{ 2, &data[4] }, { 4, &data[5] }, { 6, 0 }
};
struct llist ll1 = { &data[0] };
struct llist ll2 = { &data[3] };
struct llist ll3 = { 0 };
printf("Before:\n");
print_llist("ll1", &ll1);
print_llist("ll2", &ll2);
print_llist("ll3", &ll3);
llmrg(&ll3, &ll1, &ll2);
printf("After:\n");
print_llist("ll1", &ll1);
print_llist("ll2", &ll2);
print_llist("ll3", &ll3);
return 0;
}
I added the two assignments at the end of the llmrg() function in lieu of your two free() calls. I'm not sure whether they're necessary, but they certainly do the job. Clearly, if the list structures or node structures were dynamically allocated, then they'd need to be freed, but not in the llmrg() code.
Example output:
Before:
ll1: 1 3 5
ll2: 2 4 6
ll3:
After:
ll1:
ll2:
ll3: 1 2 3 4 5 6
Note that you can simplify the merge function considerably — 25 fewer lines of code. (It is generally easier to get small functions correct, and keep them correct. However, using the struct llnode **dest is undeniably subtle, albeit effective.) When the code contains &(*dest)->next, this is equivalent to &((*dest)->next) — the address of the next pointer pointed to by *dest.
#include <assert.h>
#include <stdio.h>
struct llnode { int item; struct llnode *next; };
struct llist { struct llnode *front; };
static
void llmrg(struct llist *dst0, struct llist *src1, struct llist *src2)
{
struct llnode *node1 = src1->front;
struct llnode *node2 = src2->front;
struct llnode **dest = &dst0->front;
src1->front = NULL;
src2->front = NULL;
while (node1 != NULL && node2 != NULL)
{
if (node1->item < node2->item)
{
*dest = node1;
node1 = node1->next;
}
else
{
*dest = node2;
node2 = node2->next;
}
dest = &(*dest)->next;
}
if (node1 != NULL)
*dest = node1;
if (node2 != NULL)
*dest = node2;
}
static void print_llist(const char *tag, struct llist *list)
{
printf("%s:", tag);
struct llnode *node = list->front;
while (node != 0)
{
printf(" %d", node->item);
node = node->next;
}
putchar('\n');
}
int main(void)
{
struct llnode data[] =
{
{ 2, &data[1] }, { 3, &data[2] }, { 5, 0 },
{ 1, &data[4] }, { 4, &data[5] }, { 6, &data[6] }, { 8, 0 },
};
struct llist ll1 = { &data[0] };
struct llist ll2 = { &data[3] };
struct llist ll3 = { 0 };
printf("Before:\n");
print_llist("ll1", &ll1);
print_llist("ll2", &ll2);
print_llist("ll3", &ll3);
llmrg(&ll3, &ll1, &ll2);
printf("After:\n");
print_llist("ll1", &ll1);
print_llist("ll2", &ll2);
print_llist("ll3", &ll3);
return 0;
}
The test data is slightly different; it would work on the original just as happily as on this data.
Example output:
Before:
ll1: 2 3 5
ll2: 1 4 6 8
ll3:
After:
ll1:
ll2:
ll3: 1 2 3 4 5 6 8