递增链表插入元素使其保持递增

Question

/*3.在一个递增有序的单链表L中插入一个值为x的元素，并保持其递增有序特性。
实验测试数据基本要求：
单链表元素为 （10,20,30,40,50,60,70,80,90,100）,
x分别为25，85，110和8
*/
#include <iostream>
#include<stdlib.h>
using namespace std;
 #define max 100
typedef int element;
typedef struct slNode {
    element data;
    struct slNode* next;
}node, * linkList;
void initialList(node*& L) {
    L = new node;
    L->next = NULL;
}
void listAdd(node*& L) {//输入一组元素
    element x = 0;
    node* u, * R;
    R = L;//尾插法
    cout << "输入链表元素(输入9999退出)：";
    cin >> x;
    while (x != 9999) {
        u = new node;
        u->data = x;
        u->next = NULL;
        R->next = u;
        R = u;
        cin >> x;
    }
}
void listPrint(node* L) {
    node* p = L->next;
    while (p != NULL) {
        cout << p->data << " ";
        p = p->next;
    }
}
void listInsert(node* L, element x) {
    node* p = L;
    node* s;
    while (p->next != NULL && p->next->data < x) {
        p = p->next;
    }
        if (x < p->next->data||p->next==NULL)
         {
            s = new node;
            s->data = x;
            s->next = p->next;
            p->next = s;
        }
 }
int main() {
    node* L;
    initialList(L);
    listAdd(L);
    element x;
;    cout << "输入要插入的元素：";
    cin >> x;
    listInsert(L, x);
    listPrint(L);
}

本来应该是一个很简单的问题，然后listInsert（）这段代码我是按着书上打的，可是为什么我输入这些，说p->next为空呢，不是已经考虑了这种情况了嘛

Answer 1

在你的listInsert()函数中，while循环的条件是p->next != NULL && p->next->data < x，这意味着只有在p->next不为NULL的情况下才会继续向下遍历链表，因此当p->next为空时，循环条件不再成立，此时循环将会终止。在这种情况下，如果直接访问p->next->data，程序将会抛出空指针异常。

要修正这个问题，你需要在循环内部检查p->next是否为空，如果为空则停止循环，然后在其后插入新节点。下面是修改后的代码：

```c++
void listInsert(node* L, element x) {
    node* p = L;
    node* s;
    while (p->next != NULL && p->next->data < x) {
        p = p->next;
    }
    if (p->next == NULL) {// 如果p已经到达链表末尾
        s = new node;
        s->data = x;
        s->next = NULL;
        p->next = s;
    }
    else {// 如果p的下一个节点的值不小于x
        s = new node;
        s->data = x;
        s->next = p->next;
        p->next = s;
    }
}
这样，当p->next为空时，程序会在链表末尾插入新节点，否则会插入新节点到p和p->next之间。

```