linked list

[dreamkk]

typedef struct node* link;
struct node { int item; link next; };

#define key(A) (A)
#define less(A, B) (key(A) <= key(B)) /* stable with code below */

link merge(link a, link b)
 { struct node head; link c = &head;
   while ((a != NULL) && (b != NULL))
     if (less(a->item, b->item))
       { c->next = a; c = a; a = a->next; }
     else
       { c->next = b; c = b; b = b->next; }
   c->next = (a == NULL) ? b : a;
   return head.next;
 }

link msort_rs(link c)
 { link a, b;
   if (c->next == NULL) return c;
   a = c; b = c->next;
   while ((b != NULL) && (b->next != NULL))
     { c = c->next; b = b->next->next; }
   b = c->next; c->next = NULL;
   return merge(msort_rs(a), msort_rs(b));
 }
main()
{
int i;
struct node heada;
link t = &heada;
for(i = 0; i < 5; i++)
{
   t->next = malloc(sizeof *t);
   t = t->next;
   t->next = NULL;
   t->item = rand() %100;
 }
 msort_rs(t);
 for(i = 0; i < 5; i++)
 {
   printf("%d", t->item);
   t = t->next;
   }
}

the msort_rs(t) doesn't sort linked list t, do i need a pointer to pointer here like
and how come when i run it the first element in the list is 65536??

link b;
..
b = msort_rs(t);

for( i =0, i < 10; i++)
{
 printf("%d", b->item);
 b = b->next;
}

[DavT]

how come when i run it the first element in the list is 65536??

you never set the value of the first element.

for(i = 0; i < 5; i++)
{
   t->next = malloc(sizeof *t);
   t = t->next;                           /* t now points to the next element in the list */
   t->next = NULL;
   t->item = rand() %100;        /* set the value in *t */
}

try this instead

for(i = 0; i < 5; i++)
{
   t->item = rand() %100;      /* set item before moving on through the list */
   t->next = malloc(sizeof *t);
   t = t->next;

}
/* set last element in the list */
t->item = rand() % 100;
t->next = NULL;

note also that at the end of the loop t points to the last element in the list so if you want to sort the whole list (rather than just the last element!) you have to do something like:

t = &heada;  /* reset t to top of list */
msort_rs(t);
for(t = &heada; t != NULL; t=t->next)
{
   printf("%d\n", t->item);
}

That should sort it I think...