Удалить узел в конце связанного списка C - PullRequest
Новая
       19

Удалить узел в конце связанного списка C

0 голосов
/ 07 октября 2019

Я написал код для удаления узла в конце связанного списка. Код работает правильно в разных тестовых случаях, но я думаю, что сделал свой код немного громоздким. Тем не менее, я не вижу, что я могу сделать по-другому? 

node_t *remove_t (node_t *l){
if (l==NULL){
    return l;
}
else {
    node_t *curr=l;
    node_t *ret=l;
    if (curr->next==NULL){
        l=NULL;
        return l;
    }
    else {
        while (curr->next->next!=NULL){
            curr=curr->next;
        }
        curr->next=NULL;
        free(curr->next);
        return ret;
    }
}
}

Ответы [ 3 ]

1 голос
/ 07 октября 2019

Намного намного проще, если вы сохраните указатель на указатель на узле, затем перейдете к концу списка и просто освободите последний указатель и установите его NULL, например 

/** delete last node */
void del_last_node (node_t **l)
{
    node_t **ppn = l;       /* pointer to pointer */
    node_t *pn = *l;        /* pointer to node */

    for (; pn->next; ppn = &pn->next, pn = pn->next) { } /* iterate to last */

    free (*ppn);           /* free node */
    *ppn = NULL;           /* set pointer NULL */
}
0 голосов
/ 07 октября 2019

Вы, кажется, не освободили хвостовой узел. 

curr->next=NULL;
free(curr->next);

Вы не сможете освободить curr-> next, если вы уже сделали его NULL.

Моя реализация: 

void remove_tail(node_t *l) {
    if (l == NULL) return;
    if (l->next == NULL) {
        free(l);
        l = NULL;
        return;
    }
    node_t *prev = l;
    node_t *curr = l->next;
    while (curr->next != NULL) {
        prev = curr;
        curr = curr->next;
    }
    prev->next = NULL;
    free(curr);
}
0 голосов
/ 07 октября 2019

Я не уверен, что вы можете сильно изменить логику - поскольку ваш подход к 3 различным случаям (пустой список, список с 1 элементом и список с> 1 элементами) является разумным. Вы можете отформатировать код для удобства чтения: что-то вроде: 

node_t *remove_t (node_t *l){
    // case 1: Empty list
    if (l==NULL){
        return l;
    } ;

    // case 2: List with one item. Return empty list.
    node_t *curr=l;
    if (curr->next==NULL){
        // Remember to free this element.
        free(curr) ;
        l=NULL;
        return l;
    } ;

    // case 3: list > one item
    // Move curr to last item
    while (curr->next->next!=NULL){
        curr=curr->next;
    }
    // Note order of free/null setting.
    free(curr->next);
    curr->next=NULL;

    return l;
}
...