c - 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;
}