c - 插入排序链表

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

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

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 个代码来处理所有情况。处理这些情况的一种常见方法是将节点放在链接列表的头部。