Merge sort 2 sorted linked list

Question

My coding skill is pretty rusty and moreover, I have never paid much attention to writing elegant code. I want to start on this. Problem is to merge 2 sorted linked list. Algorithmically this is trivial, but looks a good problem to practice coding.

struct node
{
 char *data;
 struct node *nextp;
}

typedef struct node node;
typedef struct node list; //I do 2 typedefs here to signify when conceptually I
//mean a whole list and when just a single node.is this a good practice? or only  
//one that confuses.

node * add(node *listp, char *data)
{
 node * newp=(node *)malloc(sizeof(node));
 assert(newp != NULL);
 newp->data=(char *)malloc(sizeof(strlen(data));
 assert(newp->data != NULL);
 strcpy(newp->data,data); // allocate space in newp->data . should there be +1?
 newp->next=NULL;
 if(listp==NULL) 
  listp=nextp ;
 else
  listp->nextp=newp;
 return newp;
}

list *mergelist(list * list1p, list *list2p)
{
// initialize mergedlistp;
node dummy;
node* mergedlistendp=&dummy;
list* leftlistp = NULL;

if (list1p == NULL) leftlistp=list2p;
if(list2p == NULL) leftlistp = list1p;

if(list1p != NULL && list2p!= NULL)
{
while(1)
{

 if(strcmp(list1p -> data,list2p -> data) <=0)
 {
  mergedlistendp=add (mergedlistendp,list1p->data);
  list1p=list1p -> next;
  if(list1p == NULL)
  {leftlistp=list2p; break;}
 }
 else
 {
  mergedlistendp=add (mergedlistendp,list2p->data);
  list2p=list2p -> next;
  if(list2p == NULL)
  {leftlistp=list1p; break;}
 }

}

for(leftlistp!=NULL;leftlistp = leftlistp->next) 
add(mergedlistendp,leftlistp->data);

return mergedlistendp; // I have to return mergedlistp here (i.e. head of list)
//. How to store address of mergedlistendp the first time it is assigned a value?
}

I would like my code to be reviewed.Any feedback on naming, program flow, correctness, better code, indenting, idioms etc is appreciated. Please advise on how corner cases are handled more elegantly.

Answer 1

You should have added error checking:

 node * newp=(node *)malloc(sizeof(node));
 newp->data=(char *)malloc(sizeof(strlen(data));

malloc can return NULL if there wont be enough Virtual Adress Space. Would be great if function return error code.

add {} it could bite your next time

  if(listp==NULL) 
   listp=nextp ;
  else
   listp->nextp=newp;
   //next live goes here, looks like next statment in else, but it's not.

Use PascalCase or camelCase

// initialize mergedlistp;
node* mergedlistendp=NULL; // mergedList is a better name
list* leftlistp = NULL;

Stick to one style, once you have:

if (list1p == NULL) leftlistp=list2p;
if(list2p == NULL) leftlistp = list1p;

another one

  if(listp==NULL) 
   listp=nextp ;

or

  if(list2p == NULL)
   {leftlistp=list1p; break;}

One statment per line

 if(list2p == NULL)
 {leftlistp=list1p; break;} // put break in the next line.

Answer 2

• use const when the function will not change the argument

  node * add(node *listp, const char *data)
  

• do not cast the return value of malloc(). Casting server no useful purpose and may hide errors (specifically failure to include <stdlib.h> and wrong assumptions made by the compiler about the return type)

• (subjective) add a description to assertions for more easily identify where they originate

  assert(newp != NULL && "malloc failed to create node");
  

• (subjective) one space indentation is too little