1. 如果题目没有给我们建好原递增序列的链表, 那么我们可以考虑在创建原链表时插入需要插入的结点, 就是在创建原链表时, 每读入一个数据, 将该数据与待插入的数据相比较, 如果发现待插入数据小于等于刚读入的数据, 那么就先把需要插入的数据生成的结点链接到表尾, 再把刚读入的数据结点链接到表尾, 然后继续链表的创建, 但是为了防止需要插入数据的反复插入, 我们需要设置一个标志 flag = 0; 插入完成后就将这个 flag 置为 1, 这样就不会反复插入了.
下面是这个想法的实现代码:
- #include <stdio.h>
- #include <stdlib.h>
- typedef int ElementType;
- typedef struct Node* List;
- struct Node{
- ElementType Data;
- List Next;
- };
- int main()
- {
- int N, M, dt, flag;
- flag = 0;
- List front, rear, tmp;
- front = rear = (List)malloc(sizeof(struct Node));
- scanf_s("%d %d", &N, &M);
- getchar();
- if (N == 0) // 如果原链表为空, 直接插入
- {
- tmp = (List)malloc(sizeof(struct Node));
- tmp->Data = M;
- tmp->Next = NULL;
- rear->Next = tmp;
- rear = tmp;
- }
- while (N--) // 如果原链表不为空, 在建表时插入
- {
- scanf_s("%d", &dt);
- getchar();
- if (M <= dt && flag == 0)
- {
- flag = 1;
- tmp = (List)malloc(sizeof(struct Node));
- tmp->Data = M;
- tmp->Next = NULL;
- rear->Next = tmp;
- rear = tmp;
- }
- tmp = (List)malloc(sizeof(struct Node));
- tmp ->Data = dt;
- tmp -> Next = NULL;
- rear -> Next = tmp;
- rear = tmp;
- }
- tmp = front -> Next;
- for (;tmp->Next; tmp = tmp->Next)
- printf("%d", tmp->Data);
- printf("%d\n", tmp->Data);
- return 0;
- }
2. 下面是这题的常规解法:
- List Insert(List L, ElementType X)
- {
- List PreNode, InsNode;
- PreNode = L;
- for (; PreNode->Next && PreNode->Next->Data <X; PreNode = PreNode->Next);
- InsNode = (List)malloc(sizeof(struct Node));
- InsNode->Data = X;
- InsNode->Next = PreNode->Next;
- PreNode->Next = InsNode;
- return L;
- }
来源: http://www.bubuko.com/infodetail-2798005.html