1 /*
  2  *Author: ZhangHaiba
  3  *Date: 2014-1-23
  4  *File: ordered_list_merge.c
  5  *
  6  *a demo shows merge algorithm in two ordered single linked list
  7  */
  8 
  9 #include <stdio.h>
 10 #include <stdbool.h>
 11 #include <stdlib.h>
 12 #define INF 0x7fffffff
 13 #define CMD_LNE 128
 14 
 15 typedef struct node* link;
 16 typedef struct node {
 17     int item;
 18     link next;
 19 }node;
 20 
 21 //public
 22 link NODE(int item, link next);
 23 link list_create(int n);
 24 link list_merge(link list_src_a, link list_src_b); //merge and create
 25 void list_travel(link head);
 26 void list_destroy(link head);
 27 
 28 
 29 int main(void)
 30 {
 31     int len_a, len_b;
 32 
 33     scanf("%d", &len_a);
 34     link list_a = list_create(len_a);
 35     printf("list_a travel: ");
 36     list_travel(list_a);
 37 
 38     scanf("%d", &len_b);
 39     link list_b = list_create(len_b);
 40     printf("list_b travel: ");
 41     list_travel(list_b);
 42 
 43     link list_c = list_merge(list_a, list_b);
 44     printf("list_c travel: ");
 45     list_travel(list_c);
 46 
 47     list_destroy(list_a);
 48     list_destroy(list_b);
 49     list_destroy(list_c);
 50     return 0;
 51 }
 52 
 53 link NODE(int item, link next)
 54 {
 55     link born = malloc(sizeof (node));
 56     born->item = item;
 57     born->next = next;
 58     return born;
 59 }
 60 
 61 //tail insert
 62 link list_create(int n)
 63 {
 64     int i, item;
 65     link head = NODE(INF, NULL);
 66     link tail = head;
 67 
 68     for (i = 0; i < n; ++i) {
 69         scanf("%d", &item);
 70         tail->next = NODE(item, NULL);
 71         tail = tail->next;
 72     }
 73     return head;
 74 }
 75 
 76 link list_merge(link a, link b)
 77 {
 78     link head = NODE(INF, NULL);
 79     link c = head; //c is tail pointer of list_c
 80     a = a->next;
 81     b = b->next;
 82 
 83     for (; a != NULL && b != NULL; c = c->next) {
 84         if (a->item < b->item) {
 85             c->next = NODE(a->item, NULL);
 86             a = a->next;
 87         } else {
 88             c->next = NODE(b->item, NULL);
 89             b = b->next;
 90         }
 91     }
 92     for (; a != NULL; c = c->next, a = a->next)
 93         c->next = NODE(a->item, NULL);
 94     for (; b != NULL; c = c->next, b = b->next)        
 95         c->next = NODE(b->item, NULL);
 96     return head;
 97 }
 98 
 99 void list_travel(link head)
100 {
101     for (head = head->next; head != NULL; head = head->next)
102         printf(head->next == NULL ? "%d\n" : "%d ", head->item);
103 }
104 
105 void list_destroy(link head)
106 {
107     head->next == NULL ? free(head) : list_destroy(head->next);
108 }

ZhangHaiba-MacBook-Pro:code apple$ ./a.out
6
30 53 65 77 88 99
list_a travel: 30 53 65 77 88 99
9             
11 22 33 44 55 100 120 199 211
list_b travel: 11 22 33 44 55 100 120 199 211
list_c travel: 11 22 30 33 44 53 55 65 77 88 99 100 120 199 211