链表函数排序在c

Question

我想编辑insertSortedLL链表函数

在我插入代码后，我的链表打印出来的似乎是相反的物质，例如输出:5 4 3 2 1我希望输出为1 2 3 4 5基本上问题是如何排序链表值

int insertSortedLL(LinkedList *ll, int item)
{
  insertNode(ll, 0,item);
  printList(ll);
}
void printList(LinkedList *ll) {
ListNode *cur;
if (ll == NULL)
    return;
cur = ll->head;
if (cur == NULL)
    printf("Empty");
while (cur != NULL)
{
    printf("%d ", cur->item);
    cur = cur->next;
}
printf("n");
}
void removeAllItems(LinkedList *ll)
{
ListNode *cur = ll->head;
ListNode *tmp;
while (cur != NULL) {
    tmp = cur->next;
    free(cur);
    cur = tmp;
}
ll->head = NULL;
ll->size = 0;
}
ListNode * findNode(LinkedList *ll, int index) {
ListNode *temp;
if (ll == NULL || index < 0 || index >= ll->size)
    return NULL;
temp = ll->head;
if (temp == NULL || index < 0)
    return NULL;
while (index > 0) {
    temp = temp->next;
    if (temp == NULL)
        return NULL;
    index--;
}
return temp;
}
int insertNode(LinkedList *ll, int index, int value) {
ListNode *pre, *cur;
if (ll == NULL || index < 0 || index > ll->size + 1)
    return -1;
// If empty list or inserting first node, need to update head pointer
if (ll->head == NULL || index == 0) {
    cur = ll->head;
    ll->head = malloc(sizeof(ListNode));
    ll->head->item = value;
    ll->head->next = cur;
    ll->size++;
    return 0;
}
// Find the nodes before and at the target position
// Create a new node and reconnect the links
if ((pre = findNode(ll, index - 1)) != NULL) {
    cur = pre->next;
    pre->next = malloc(sizeof(ListNode));
    pre->next->item = value;
    pre->next->next = cur;
    ll->size++;
    return 0;
}
return -1;
}
int removeNode(LinkedList *ll, int index) {
ListNode *pre, *cur;
// Highest index we can remove is size-1
if (ll == NULL || index < 0 || index >= ll->size)
    return -1;
// If removing first node, need to update head pointer
if (index == 0) {
    cur = ll->head->next;
    free(ll->head);
    ll->head = cur;
    ll->size--;
    return 0;
}
// Find the nodes before and after the target position
// Free the target node and reconnect the links
if ((pre = findNode(ll, index - 1)) != NULL) {
    if (pre->next == NULL)
        return -1;
    cur = pre->next;
    pre->next = cur->next;
    free(cur);
    ll->size--;
    return 0;
}
return -1;
}

Answer 1

insertSortedLL()函数应该在正确的位置将节点插入到排序列表中。如果使用此函数构建列表，则生成的列表将被排序。

您的insertSortedLL()函数需要遍历列表，将每个节点的item与您想要插入的item进行比较。将项插入到包含大于插入值的第一个节点的位置，或者插入到列表的末尾。下面是一个如何书写的例子:

int insertSortedLL(LinkedList *ll, int item)
{
    ListNode *cur = ll->head;
    int ll_size = ll->size;
    int i;
    for (i = 0; i <= ll_size; i++) {
        if ((ll_size - i) == 0 || item < cur->item) {
            insertNode(ll, i, item);
            return 0;
        }
        cur = cur->next;
    }
    return -1;
}