list_merge.c

#include<stdio.h>
#include<stdlib.h>

struct list_node {
  int val;
  struct list_node *next;
};

int node_size = sizeof(struct list_node);

struct list_node* allocate_node() {
  return malloc(node_size);
}

struct list_node* add_items(struct list_node *current_head, int *items, int N) {
  for(int i=N-1; i>=0; i--) {
    struct list_node *new_head = allocate_node();
    new_head->val = items[i];
    new_head->next = current_head;
    current_head = new_head;
  }
  return current_head;
}

void print_list(struct list_node *head) {
  while (head) {
    printf("%d -> ", head->val);
    head = head->next;
  }
  printf("X\n");
}

void free_list(struct list_node *head) {
  while (head) {
    struct list_node *next_head = head->next;
    free(head);
    head = next_head;
  }
}

struct list_node *merge_lists(struct list_node *l1, struct list_node *l2) {
  struct list_node *result_head = NULL;

  /* check for null lists */
  if (!l1) {
    return l2;
  }
  else if (!l2) {
    return l1;
  }
  else {
    /* initialize the return list */
    if (l1->val < l2->val) {
      result_head = l1;
      l1 = l1->next;
    }
    else {
      result_head = l2;
      l2 = l2->next;
    }

    /* traverse the lists */
    struct list_node *node = result_head;
    while (l1 && l2) {
      if (l1->val < l2->val) {
	node->next = l1;
	l1 = l1->next;
      }
      else if (l2) {
	node->next = l2;
	l2 = l2->next;
      }
      node = node->next;
    }

    /* append whatever is left */
    if (l1) {
      node->next = l1;
    }
    else {
      node->next = l2;
    }
  }

  return result_head;
}

int main(void) {
    
  /* initialization */
  int l1_items[] = {1, 5, 9};
  int l2_items[] = {2, 3, 7, 10};
  struct list_node *l1_head = add_items(NULL, l1_items, 3);
  printf("list A:\n");
  print_list(l1_head);
  
  struct list_node *l2_head = add_items(NULL, l2_items, 4);
  printf("list B:\n");
  print_list(l2_head);

  /* merging */
  printf("merged A and B:\n");
  struct list_node *merged = merge_lists(l1_head, l2_head);
  print_list(merged);
  free_list(merged);
}