Code duplication

Question

I wrote a function that merges two linked lists but I seem to have some code duplication I'm not sure what to do with:

//merges two sorted linked lists into *merged_out, returns suitable error/success codes
ErrorCode mergeSortedLists(Node list1, Node list2, Node *merged_out)
{
 if(!merged_out){
 return NULL_ARGUMENT;
 }
 if((!list1) || (!list2)){
 return EMPTY_LIST;
 }
 if(!(isListSorted(list1) && isListSorted(list2))){
 return UNSORTED_LIST;
 }
 Node *tmp = merged_out; //We use temp in order to keep a pointer to the first node (merged_out)
 int length = getListLength(list1) + getListLength(list2);
 //The first merging iteration is special because we have to run over
 //the current Node, so we don't have an extra 1 at the beginning
 if(list1->x < list2->x){
 (*tmp) = createNode(list1->x);
 if((*tmp) == NULL){
 destroyList(*merged_out);
 return MEMORY_ERROR;
 }
 list1 = list1->next;
 }
 else{
 (*tmp) = createNode(list2->x);
 if((*tmp) == NULL){
 destroyList(*merged_out);
 return MEMORY_ERROR;
 }
 list2 = list2->next;
 }
 //Now we do the same check without running over the Node, iterating through both lists
 for(int i=0; i<length-1; i++){
 assert(tmp);
 if(!list1){
 (*tmp)->next = createNode(list2->x);
 if((*tmp)->next == NULL){
 destroyList(*merged_out);
 return MEMORY_ERROR;
 }
 tmp = &((*tmp)->next);
 list2 = list2->next;
 continue;
 }
 if(!list2){
 (*tmp)->next = createNode(list1->x);
 if((*tmp)->next == NULL){
 destroyList(*merged_out);
 return MEMORY_ERROR;
 }
 tmp = &((*tmp)->next);
 list1 = list1->next;
 continue;
 }
 if(list1->x < list2->x){
 (*tmp)->next = createNode(list1->x);
 if((*tmp)->next == NULL){
 destroyList(*merged_out);
 return MEMORY_ERROR;
 }
 tmp = &((*tmp)->next);
 list1 = list1->next;
 }
 else
 {
 (*tmp)->next = createNode(list2->x);
 if((*tmp)->next == NULL){
 destroyList(*merged_out);
 return MEMORY_ERROR;
 }
 tmp = &((*tmp)->next);
 list2 = list2->next;
 }
 }
 return SUCCESS;
}

the parts such as:

(*tmp)->next = createNode(list1->x);
 if((*tmp)->next == NULL){
 destroyList(*merged_out);
 return MEMORY_ERROR;
 }
 tmp = &((*tmp)->next);
 list1 = list1->next;

are very repetitive, any tips for what I should do with them? creating a function to do it seems kinda ugly because i'll have to pass on many pointers, maybe some sort of macro would work?

**Additional parts requested:

enum definition:

typedef enum {
SUCCESS=0,
MEMORY_ERROR,
EMPTY_LIST,
UNSORTED_LIST,
NULL_ARGUMENT,
} ErrorCode;

functions:

bool isListSorted(Node list) {
 if (list == NULL) {
 return true;
 }
 int prev = list->x;
 list = list->next;
 while (list != NULL) {
 if (prev > list->x) {
 return false;
 }
 prev = list->x;
 list = list->next;
 }
 return true;
}
//Frees all memory allocated to list starting at ptr
void destroyList(Node ptr){
 while(ptr){
 Node to_delete = ptr;
 ptr = ptr->next;
 free(to_delete);
 }
}
//Creates a Node with x=num and returns its &
Node createNode(int num){
 Node ptr = malloc(sizeof(*ptr));
 if(!ptr){
 return NULL;
 }
 ptr->x = num;
 ptr->next = NULL;
 return ptr;
}
```

• pacmaninbw: Welcome to code review, we would need to see more of the program to be able to properly review it. Specifically we need to see the functions that call this function, the definitions of NULL_ARGUMENT, EMPTY_LIST, UNSORTED_LIST and SUCCESS. We would also need to see the functions destroyList(), createNode() and isListSorted().

Answer 1

• Normally, merging lists is done in place by relinking the next pointers. If you want to keep the original lists intact, I recommend to make theirs copies, and merge copies in an idiomatic way. This way the actual merge doesn't need to worry about memory problems.

  Try it and see how the SRP shines here. It should address your immediate problem with code duplication.

• It is perfectly all right to merge a list with an empty one. It is also all right to merge two empty lists. Failing in

   if((!list1) || (!list2)){
   return EMPTY_LIST;
   }
  

  is not correct.

• There is no point to precompute the length of the merged list. The idiomatic way is to split merging into two phases:

  /* An actual merge...*/
  while (list1 && list2) {
   ....
  }
  /* ...followed by appending the data from a non-empty list. */
  /* Notice that you shouldn't even care which list is not empty */
  while (list1) {
   .... /* append data from list1 to the merged list */
  }
  while (list2) {
   .... /* append data from list2 to the merged list */
  }
  

  It is worth mentioning that the last two loops are identical, and should be factored out into a function of its own right.

• The special case of the very first iteration can be avoided by using a dummy head. I presume that you have a definition along the lines of

   struct node {
   some_type x;
   struct node * next;
   };
  

  (which is further typedef struct node * Node). Declare a

   struct node merged_head_dummy;
  

  and eventually return merged_head_dummy.next. See how the special case disappears.

  BTW, this is a strong case against hiding a pointer behind a typedef.

• There is no need to parenthesize (*tmp).

• user11555739: Hey, thanks for all your notes! I understood most of them and they make sense. I probably should have mentioned this is a homework project to my university so I can't change some of the stuff you mentioned such as typedefing a pointer and checking for empty lists (because those are the instructions). could you elaborate on how you would use a function for the while loops?