插入排序链表

Question

尝试编写一个函数，要求用户输入一个整数，然后按升序将其插入到链表中。

typedef struct _listnode{
    int item;
    struct _listnode *next;
} ListNode;         

typedef struct _linkedlist{
    int size;
    ListNode *head;
} LinkedList;           

void insertSortedLinkedList(LinkedList *l)
{
    ListNode *cur;
    int x;
    printf("please input an integer you want to add to the linked list:");
    scanf("%d", &x);

    if (l->head == NULL) // linkedlist is empty, inserting as first element
    {
        l->head = malloc(sizeof(ListNode));
        l->head->item = x;
        l->head->next = NULL;
    }
    else
    {
        cur = l->head;
        if (x < cur->item) // data is smaller than first element, we will insert at first element and update head.
        {
            cur->next->item = cur->item; // store current element as next element.
            cur->item = x;
            cur->next = cur->next->next;
        }
    }
    l->size++;
}

功能还没有完成，但是如果数据小于第一个元素，为什么我的代码不起作用？

Answer 1

插入函数的 else 分支假定 cur->next 不是 NULL（因为您将值设置为 cur->next->item）。现在想象插入两个数字（第二个比第一个小）。在第一次插入时，l->head->next 被设置为 NULL。因此，在第二次插入时，程序将在尝试将 cur->next->item 设置为某个值时崩溃。您应该创建一个节点（即通过 malloc() 分配内存），根据需要初始化节点以包含字段，然后将其设置为 cur->next.

Answer 2

首先您需要为新元素创建节点，如下所示：

ListNode* newNode =  malloc(sizeof(ListNode));
newNode ->item = x;

现在更改您的代码：

if (x < l->head->item) // data is smaller than first element, we will insert at first element and update head.
    {
        newNode->next = l->head;
        l->head = newNode;
    }
}

就像你说的代码不完整是的，循环遍历列表，直到找到插入新节点的正确位置。

可以编写 1 个代码来处理所有情况。处理这些情况的一种常见方法是将节点放在 link 列表的头部。

插入排序链表

Insert sorted linked list

c

linked-list