My code is supposed stores 10 int numbers in a linked list, divide these 10 numbers equally into two other linked lists. But my two lists are returning empty
My struct:
typedef struct no
{
int value;
struct no *next;
} no;
The variable size comes from a function that loops through my main list and returns its size. Then created two "almost equal" functions to take the value from the main list and store it in the ListB and ListC.
My functions:
no* copylist(no *list, no *listReceive,int size)
{
no *aux = list;
no *receive=listReceive;
int count=0;
while(aux!=NULL&&count<size/2)
{
insert(receive, aux->value);
aux=aux->next;
}
count = size/2;
return receive;
}
no* copylist1(no *list, no *listReceive,int size)
{
no *aux = list;
no *receive=listReceive;
int count=0;
while(aux!=NULL&&count<size/2)
{
aux=aux->next;
count ;
}
count = size/2;
aux=aux->next;
while(aux!=NULL&&count<size)
{
insert(receive, aux->value);
aux=aux->next;
}
return receive;
}
Obs: for me linked lists is a very confusing content
CodePudding user response：
The split can be done in a single pass if we use two pointers. One that traverses via cur1 = cur1->next and another that traverses twice as fast (e.g. cur2 = cur2->next->next);
When cur2 reaches the end, cur1 will be at the midpoint.
When we pass a "single star" pointer that is the list start to a function that must adjust and return the head of the list, the adjustment will not be reflected back to the caller.
Rather than pass down "double star" pointers for this lists, it's easier/better to use a separate list struct in addition to the node struct.
Note that we could co-opt/reuse a [dummy] node as the list pointer, but it's more clear if we use the separate struct.
Below is some annotated code. Unfortunately, I had to refactor a good deal of it to get it to work.
Here is a version that does [depending on the program argument]:
- A simple two pass version. One to compute the count and a second pass to do the split based on that count
- An improved version that does the split in a single pass by using the "two pointer" technique mentioned above
#include <stdio.h>
#include <stdlib.h>
int passno;
// node
typedef struct no {
int value;
struct no *next;
} no;
// list
typedef struct li {
no *head;
} li;
// show -- show a list
void
show(li *lst,const char *sym)
{
printf("%s:",sym);
for (no *cur = lst->head; cur != NULL; cur = cur->next)
printf(" -",cur->value);
printf("\n");
}
// newlist -- create a new list with N elements
li *
newlist(int count)
{
li *lst = malloc(sizeof(*lst));
no *cur;
no *prev;
lst->head = NULL;
prev = NULL;
for (int idx = 0; idx < count; idx) {
cur = malloc(sizeof(*cur));
cur->next = NULL;
cur->value = idx 1;
if (prev != NULL)
prev->next = cur;
else
lst->head = cur;
prev = cur;
}
return lst;
}
// lstcount -- count number of elements in the list
int
lstcount(li *lst)
{
no *cur;
int count = 0;
for (cur = lst->head; cur != NULL; cur = cur->next)
count;
return count;
}
// splitA -- split a list into two halves (single pointer, two pass version)
void
splitA(li *lstleft,li *lstright,li *lstfrom)
{
int count;
int idx;
no *cur;
no *left;
count = lstcount(lstfrom);
count = (count 1) / 2;
left = NULL;
lstleft->head = NULL;
idx = 0;
for (cur = lstfrom->head; cur != NULL; cur = cur->next) {
if ( idx > count)
break;
// append to left list
if (left == NULL)
lstleft->head = cur;
left = cur;
}
// disconnect/cut the tail of the left list from the right list
if (left != NULL)
left->next = NULL;
// start the right list
lstright->head = cur;
// zap the original list
lstfrom->head = NULL;
}
// splitB -- split a list into two halves (two pointer, one pass version)
void
splitB(li *lstleft,li *lstright,li *lstfrom)
{
no *cur1;
no *cur2;
no *left;
left = NULL;
lstleft->head = NULL;
cur2 = lstfrom->head;
for (cur1 = lstfrom->head; cur1 != NULL; cur1 = cur1->next) {
// wait for double speed pointer to end
if (cur2 == NULL)
break;
cur2 = cur2->next;
// append to left list
if (left == NULL)
lstleft->head = cur1;
left = cur1;
// advance at twice the rate
if (cur2 != NULL)
cur2 = cur2->next;
}
// disconnect/cut the tail of the left list from the right list
if (left != NULL)
left->next = NULL;
// start the right list
lstright->head = cur1;
// zap the original list
lstfrom->head = NULL;
}
// clean -- free up list elements and list descriptor
void
clean(li *lst)
{
no *cur;
no *next;
for (cur = lst->head; cur != NULL; cur = next) {
next = cur->next;
free(cur);
}
free(lst);
}
// dotest -- test the split for a given number of nodes
void
dotest(int count)
{
li *big;
li *left;
li *right;
printf("\n");
printf("dotest: count=%d\n",count);
big = newlist(count);
show(big,"big");
left = newlist(0);
right = newlist(0);
switch (passno) {
case 1:
splitA(left,right,big);
break;
case 2:
splitB(left,right,big);
break;
}
show(left,"lhs");
show(right,"rhs");
clean(left);
clean(right);
clean(big);
}
int
main(int argc,char **argv)
{
--argc;
argv;
if (argc > 0)
passno = atoi(*argv);
if (passno <= 0)
passno = 1;
if (passno > 2)
passno = 2;
printf("passno=%d\n",passno);
for (int count = 0; count <= 12; count)
dotest(count);
}
Here is the program output:
passno=1
dotest: count=0
big:
lhs:
rhs:
dotest: count=1
big: 1
lhs: 1
rhs:
dotest: count=2
big: 1 2
lhs: 1
rhs: 2
dotest: count=3
big: 1 2 3
lhs: 1 2
rhs: 3
dotest: count=4
big: 1 2 3 4
lhs: 1 2
rhs: 3 4
dotest: count=5
big: 1 2 3 4 5
lhs: 1 2 3
rhs: 4 5
dotest: count=6
big: 1 2 3 4 5 6
lhs: 1 2 3
rhs: 4 5 6
dotest: count=7
big: 1 2 3 4 5 6 7
lhs: 1 2 3 4
rhs: 5 6 7
dotest: count=8
big: 1 2 3 4 5 6 7 8
lhs: 1 2 3 4
rhs: 5 6 7 8
dotest: count=9
big: 1 2 3 4 5 6 7 8 9
lhs: 1 2 3 4 5
rhs: 6 7 8 9
dotest: count=10
big: 1 2 3 4 5 6 7 8 9 10
lhs: 1 2 3 4 5
rhs: 6 7 8 9 10
dotest: count=11
big: 1 2 3 4 5 6 7 8 9 10 11
lhs: 1 2 3 4 5 6
rhs: 7 8 9 10 11
dotest: count=12
big: 1 2 3 4 5 6 7 8 9 10 11 12
lhs: 1 2 3 4 5 6
rhs: 7 8 9 10 11 12