两个有序链表合成一个有序链表

  1 /*
  2     无聊帮朋友撸个作业。。。。。。 \ = v = / 
  3 
  4     两个有序链表合成为一个有序链表.
  5     要求：
  6         1. 每个链表元素里的值不超过int范围.
  7         2. 两个链表要求为升序（从小到大).
  8 
  9 
 10                             2016.1.5   author : 加德满都的猫会爬树 
 11 
 12 */
 13 
 14 #include <iostream>
 15 using namespace std;
 16 const int MAX = 100000;
 17 int save[MAX];
 18 struct node
 19 {
 20     int val;
 21     node * next ;
 22 };
 23 node * creat(int n , int * arr) // 根据 arr 数组中的 前 n 个数字 生成一条链表 
 24 {
 25     if(!n) return NULL;
 26     node * root = new node;
 27     root -> val = arr[0];
 28     root -> next = NULL;
 29     node * pre = root ;
 30     for(int i = 1 ; i < n ; i++)
 31     {
 32         node * tmp = new node ;
 33         tmp -> val = arr[i];
 34         tmp -> next = NULL;
 35 
 36         pre -> next = tmp;
 37         pre = tmp;
 38     }
 39     return root ;
 40 }
 41 void show(node * in) // 显示函数， 按顺序输出一条链表。
 42 {
 43     while(in != NULL)
 44     {
 45         cout << in -> val << " " ;
 46         in = in -> next;
 47     }
 48     cout << endl;
 49     return ;
 50 }
 51 void combine(node * A , node * B) // 合并两个链表，将 B 合成 至 A 链表上 
 52 {
 53     if(A == NULL && B == NULL) return ; // 如果两个链表皆为空 ， 返回 。
 54     if(A == NULL) // 如果 A 链表为空， 则 合并结果就为 B 链表。 
 55     {
 56         A = B;
 57         return ;
 58     }
 59     if(B == NULL) return ; // 如果 B 链表为空， 合并结果就为 A 链表。
 60 
 61     node * p1 = A , * cur = B ;
 62     while(cur != NULL && p1 -> val > cur -> val)
 63     {
 64         node * tmp = cur ;
 65         cur = cur -> next;
 66         tmp -> next = p1;
 67         p1 = tmp;
 68     }
 69     node * p2 = p1 -> next;
 70     while(cur != NULL)
 71     {
 72         if(p2 == NULL)
 73         {
 74             p1 -> next = cur;
 75             cur = NULL ;
 76             continue;
 77         }
 78         if(cur -> val < p2 -> val)
 79         {
 80             node * tmp = cur ;
 81             cur = cur -> next;
 82             p1 -> next = tmp;
 83             tmp -> next = p2;
 84             p1 = p1 -> next;
 85             continue;
 86         }
 87         p1 = p1 -> next;
 88         p2 = p2 -> next;
 89     }
 90     return ;
 91 }
 92 int main()
 93 {
 94     int n;
 95     cout << "请输入第一个链表的长度(数字个数) : ";
 96     cin >> n;
 97     if(n)
 98     {
 99         cout << "请输入第一个链表里的数字，" << n << " 个. 空格隔开 : " ;
100         for(int i = 0 ; i < n ; i++) cin >> save[i];
101     }
102     node * A = creat(n , save);
103 
104     cout << "请输入第二个链表的长度(数字个数) : ";
105     cin >> n;
106     if(n)
107     {
108         cout << "请输入第二个链表里的数字，" << n << " 个. 空格隔开 : " ;
109         for(int i = 0 ; i < n ; i++) cin >> save[i];
110     }
111     node * B = creat(n , save);
112     
113     combine(A , B);
114     cout << "合并后的结果 : " << endl;
115     show(A);
116 
117     return 0;
118 
119 }