题目链接：https://pintia.cn/problem-sets/434/problems/5726
1.如果题目没有给我们建好原递增序列的链表，那么我们可以考虑在创建原链表时插入需要插入的结点，就是在创建原链表时，每读入一个数据，将该数据与待插入的数据相比较，如果发现待插入数据小于等于刚读入的数据，那么就先把需要插入的数据生成的结点链接到表尾，再把刚读入的数据结点链接到表尾，然后继续链表的创建，但是为了防止需要插入数据的反复插入，我们需要设置一个标志flag = 0; 插入完成后就将这个flag置为1，这样就不会反复插入了。
下面是这个想法的实现代码：
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 typedef int ElementType; 5 typedef struct Node* List; 6 struct Node{ 7 ElementType Data; 8 List Next; 9 }; 10 11 int main() 12 { 13 int N, M, dt, flag; 14 flag = 0; 15 List front, rear, tmp; 16 front = rear = (List)malloc(sizeof(struct Node)); 17 18 scanf_s("%d %d", &N, &M); 19 getchar(); 20 21 if (N == 0) //如果原链表为空，直接插入 22 { 23 tmp = (List)malloc(sizeof(struct Node)); 24 tmp->Data = M; 25 tmp->Next = NULL; 26 rear->Next = tmp; 27 rear = tmp; 28 } 29 30 while (N--) //如果原链表不为空，在建表时插入 31 { 32 scanf_s("%d", &dt); 33 getchar(); 34 if (M <= dt && flag == 0) 35 { 36 flag = 1; 37 tmp = (List)malloc(sizeof(struct Node)); 38 tmp->Data = M; 39 tmp->Next = NULL; 40 rear->Next = tmp; 41 rear = tmp; 42 } 43 tmp = (List)malloc(sizeof(struct Node)); 44 tmp ->Data = dt; 45 tmp -> Next = NULL; 46 rear -> Next = tmp; 47 rear = tmp; 48 } 49 tmp = front -> Next; 50 for (;tmp->Next; tmp = tmp->Next) 51 printf("%d ", tmp->Data); 52 printf("%d\n", tmp->Data); 53 54 55 return 0; 56 }
2.下面是这题的常规解法：
1 List Insert(List L, ElementType X) 2 { 3 List PreNode, InsNode; 4 PreNode = L; 5 for (; PreNode->Next && PreNode->Next->Data < X; PreNode = PreNode->Next); 6 InsNode = (List)malloc(sizeof(struct Node)); 7 InsNode->Data = X; 8 InsNode->Next = PreNode->Next; 9 PreNode->Next = InsNode; 10 return L; 11 }
