Removing all nodes with a certain value in a linke

问题:

The title is pretty self explanatory. Here's the function I've written for this purpose:

void wipeLoneCells()
{
    cell *tmp;

    tail = head;
    while (1)
    {
        if (head == tail && !tail->flag)
        {
            head = head->next;
            free(tail);
            tail = head;
            continue;
        }

        tmp = tail->next;

/***/   if (tmp->next == NULL && !tmp->flag)
        {
            tail->next = NULL;
            free(tmp);
            break;
        }
        else if (!tmp->flag)
        {
            tail->next = tmp->next;
            free(tmp);
            continue;
        }

        tail = tail->next;      
    }
}

The list's head and tail are global, and the list is built by the time this function gets called with head pointing to the first node and tail pointing to the last (whose next is NULL). I'm almost certain that my linked list is built correctly as I can print them with no errors. Sometimes this function works perfectly and sometimes it results in an access violation at the line marked with stars. I know it's not completely wrong as I do get the result I want when it doesn't produce an error, although I do get the error frequently so there must be something I'm overlooking. Thank you in advance for any help.

EDIT: Here's the fixed code:

void wipeLoneCells()
{
    cell *tmp;

    tail = head;
    while (1)
    {
        if (head == tail && !tail->flag)
        {
            head = head->next;
            free(tail);
            tail = head;
            continue;
        }

        tmp = tail->next;

        if (tmp->next == NULL && !tmp->flag)
        {
            tail->next = NULL;
            free(tmp);
            break;
        }
        else if (tmp->next == NULL)
        {
            tail = tmp;
            break;
        }
        else if (!tmp->flag)
        {
            tail->next = tmp->next;
            free(tmp);
            continue;
        }

        tail = tail->next;      
    }
}

回答1:

What if

tmp = tail->next; 

is NULL? The next line attempts to dereference a NULL pointer, which results in undefined behavior - possibly leading to a crash.

You should check for this condition and take appropriate action.

回答2:

The correct deleteitem() in a singly linked list should be as follows:

You can avoid the recursion and come up with an iterative version (give it a try but let me know if you need help). I wouldn't use a while(1) for this case!

typedef struct node {
    int data;
    struct node *next;
}NODE;


/*

(1) deleting head 
    delete element and adjust head pointer

(2) deleting tail
    delete element and adjust tail pointer

(3) one element list
    if data is the data for the only element
    then delete the list and set head and tail
    pointers to NULL

(4) all the other cases
    traverse through the list and hold the
    previous pointer. delete element and adjust
    the next pointers. 

(5) if not the above cases, then element not
    present.. do nothing..

*/
void deleteitem(int data)
{
    printf("%s: %d - ", __FUNCTION__, data);
    NODE *cur = head;
    NODE *prev = cur;
    NODE *temp = NULL;

    if (head == NULL) {
        assert (tail == NULL);
        printf("Empty list \n");
        return;
    }

    if (head->data == data) {
        temp = head;

        // one element list
        if (head == tail)
            head = tail = NULL;
        else
            // list has more than one element
            head = head->next;

        printf("%d \n", temp->data);
        free(temp);
        deleteitem(data);
        return;
    }

    while (cur != NULL) {
        if (cur->data == data) {
            if (cur == tail) {
                tail = prev;
            }
            prev->next = cur->next;
            printf(" %d deleted\n", cur->data);
            free(cur);
            assert(tail->next == NULL);
            deleteitem(data);
            return;
        }
        prev =cur;
        cur = cur->next;
    }

    printf(" %d not found\n", data);
    return;
}