Обновление связанного списка по указателю внутри функции

Question

Мне не хватает связанного списка, и я пытаюсь создать функцию, которая будет извлекать все нечетные числа из ссылки и создавать с ними новый связанный список.

Дело в том, что яЯ не понимаю, как обновить исходный список с помощью указателя на функцию, на самом деле я до сих пор делал новый список с нечетными числами, но я не совсем понимаю, как «удалить» их из исходного списка и связать все остальные вместе., а затем отправьте его обратно на главную.

Node *build_odd_list(Node *oldlst, Node *newlst) {
    Node *temp, *curheadNew;
    temp = (Node*)malloc(sizeof(Node));

    if (oldlst->value % 2 != 0) {
        temp->next = NULL;
        temp->value = oldlst->value;
        newlst = temp;
        curheadNew = newlst;
        oldlst = oldlst->next;
        printf("Passed %d\n", curheadNew->value);
    }
    else {
        oldlst = oldlst->next;
    }
    while (oldlst) {
        if (oldlst->value % 2 != 0) {
            temp = (Node*)malloc(sizeof(Node));
            temp->value = oldlst->value;
            temp->next = NULL;
            curheadNew->next = temp;
            curheadNew = curheadNew->next;
            oldlst = oldlst->next;
            printf("Passed %d\n", curheadNew->value);
        }
        else {
            oldlst = oldlst->next;
        }
    }
    return newlst;
}

Большое спасибо!

Answer 1

Так как вам нужно вернуть новый список, содержащий нечетные числа, и изменить исходный список из-за удаления нечетных чисел, вам необходимо передать вызывающему два значения: указатель на первый элемент обновленного оригинала. list и указатель на первый элемент списка «нечетных чисел».

Так как вам все равно нужно передать исходный список в функцию, самый простой вариант для этой функции:

• передать указатель на указатель на первый элемент исходного списка;
• изменить исходный список с помощью указателя;
• возвращает указатель на первый элемент списка «нечетных чисел», извлеченного из исходного списка.

Нет необходимости выделять какие-либо новые элементы для списка «нечетных чисел», поскольку элементы с нечетными номерами можно перемещать из одного списка в другой.

Стоит изучить трюк «указатель на указатель», так как это обычный способ манипулирования указателями списка.

Вот пример программы, иллюстрирующей описанный выше метод. Обратите особое внимание на функцию extract_odd_list() и вызов этой функции из main().

#include <stdio.h>
#include <stdlib.h>

typedef struct _Node {
    int value;
    struct _Node *next;
} Node;

/* Move odd numbers in *list to returned list. */
Node *extract_odd_list(Node **list) {
    Node *oddstart = NULL;      /* start of returned list */
    Node **oddend = &oddstart;  /* pointer to final link of returned list */

    while (*list) {
        if ((*list)->value % 2 != 0) {
            /* Current element of original *list is odd. */
            /* Move original *list element to end of returned list. */
            *oddend = *list;
            /* Bypass moved element in original list. */
            *list = (*list)->next;
            /* Update pointer to final link of returned list. */
            oddend = &(*oddend)->next;
        }
        else {
            /* Current element of original *list is even. */
            /* Skip to next element of original *list. */
            list = &(*list)->next;
        }
    }
    /* Terminate the returned list. */
    *oddend = NULL;
    /* And return it. */
    return oddstart;
}

void *printlist(Node *list) {
    while (list) {
        printf(" %d", list->value);
        list = list->next;
    }
}

int main(void) {
    int i;
    Node *list = NULL;
    Node *end = NULL;
    Node *oddlist;
    Node *temp;

    /* Construct a list containing odd and even numbers. */
    for (i = 1; i <= 10; i++) {
        temp = malloc(sizeof(*temp));
        temp->value = i;
        if (end == NULL) {
            list = temp;
        }
        else {
            end->next = temp;
        }
        end = temp;
    }
    end->next = NULL;
    printf("Original list:");
    printlist(list);
    printf("\n");

    /* Move the "odd number" elements from the original list to a new list. */
    oddlist = extract_odd_list(&list);

    printf("Updated list:");
    printlist(list);
    printf("\n");

    printf("Odd list:");
    printlist(oddlist);
    printf("\n");
    return 0;
}