将一个数字插入到已排序的链表中，为什么每次都将数字插入到第二个位置？

debugcn 发表于 Dev

Yizhi Hu

我正在做一个关于链表的项目，我在将一个数字插入到一个排序的链表中时遇到了麻烦。每次插入到第二个位置的数字，我都想不通问题出在哪里。这是我的代码：

void insertSort(struct linkedList *n,int num,int *length){                   //insert number to a sort linked list
    node *new = (node *) malloc(sizeof(node));          //create a new node
    new->next=NULL;
    new->data = num;
    while(n!=NULL&&n->data > new->data){             // find which position     num should insert in sorted list
            n = n->next;
    }
    new->next = n->next;          
    n->next= new;       
    length += 1;

}

n 是链表的头部。我初始化 head 指向第一个节点并且没有值。这是我调用此函数的方式：

insertSort(head->next,num,&length);

每次插入到第二个位置的数字。就像我想将 45 插入到已排序的链表 <16,32,72,81,97> 中，插入后，列表将是 <16,45,32,72,81,97>。45 出于某种原因插入到第二个位置。

问题：

每次插入到第二个位置的数字...

正在发生是因为在这部分代码中：

while(n!=NULL&&n->data > new->data){             // find which position     num should insert in sorted list
        n = n->next;
}
new->next = n->next;          
n->next= new;

您在n->next.

假设你的链表的第一个节点有数据16，现在你想45在链表中插入带有数据的新节点，while循环条件将失败，16 > 45评估结果为false。

并且while循环之后的语句new->next = n->next;会将新节点的下一个设置为第一个节点的下一个，并将在第一个n->next= new;节点之后插入新节点。因此，新节点每次都插入到第二个位置。

您的功能还有一些问题，insertSort()例如：

在head向链表中插入节点时，它不跟踪链表的，并且，
如果插入的节点是链表的第一个节点会发生什么？在这种情况下，nwillNULL并且在insertSort()afterwhile循环中访问的next是n- new->next = n->next;。

查看您给出的示例 - <16,32,72,81,97>，您想按升序插入。你可以做：

struct linkedList *insertSort(struct linkedList *n, int num, int *length) {
    struct linkedList *first_node = n;

    struct linkedList *new_node = malloc(sizeof(struct linkedList));  //create a new node
    new_node->next=NULL;
    new_node->data = num;

    if (first_node == NULL || first_node->data >= new_node->data) {
            new_node->next = first_node;
            first_node = new_node;
    } else {
            struct linkedList *temp = first_node;

            while (temp->next != NULL && temp->next->data < new_node->data) {
                    temp = temp->next;
            }
            new_node->next = temp->next;
            temp->next = new_node;
    }
    *length += 1;

    return first_node;
}

在这里，您可以看到我已将返回类型更改void为，struct linkedList *以便在将新节点插入链表中的适当位置insertSort()后将返回head链表的。这样你就可以head在每次插入后跟踪链表。你只需要做：

head = insertSort(head, num, &length);

无论您在哪里打电话insertSort()。

或者，您可以将head指针的地址传入insertSort()并跟踪它，如果您不想更改的返回类型insertSort()，如下所示：

void insertSort(struct linkedList **head, int num, int *length) {
    struct linkedList *new_node = malloc(sizeof(struct linkedList));  //create a new node
    new_node->next=NULL;
    new_node->data = num;

    if (*head == NULL || (*head)->data >= new_node->data) {
        new_node->next = *head;
        *head = new_node;
    } else {
        struct linkedList *temp = *head;

        while (temp->next != NULL && temp->next->data < new_node->data) {
                temp = temp->next;
        }
        new_node->next = temp->next;
        temp->next = new_node;
    }
    *length += 1;
}

你可以这样调用insertSort()：