I successfully implemented a function but with a minor bug I can't figure out. The function filter() takes in a list

(Ex. lst = [4, 9, 2, 4, 8, 12, 7, 3]) and a value (value = 4).

It is expected to put all elements below the value into a new list. So the output will be

(Ex. lst = [9, 8, 12, 7] and new_lst = [4, 2, 4, 3].

HOWEVER, my program returns

lst = [9, 8, 12, 7, 3] and new_lst = [4, 2, 4, 3]

instead. I notice that's because the last value is 3 which is lesser or equals to value = 4. On the contrary, when the last value of the list is greater than value = 4

(Ex. lst = [4, 9, 2, 4, 8, 12, 7, 5]).

Then, I get a output like this

lst = [lst: [9, 8, 12, 7, 5] and new_lst: [4, 2, 4, 8, 12, 7 ,5].

// Structure of my linked list and node for reference
typedef struct node {
    int val;
    struct node *next;
} NODE;

struct list_struct {
    NODE *front;
    NODE *back;
};

// The function with the bug
LIST *filter(LIST *lst, int value) {
    LIST *new_list = lst_create();
    NODE *p = lst->front;
    NODE *p1 = NULL;
    NODE *p2 = NULL;
    while (p != NULL) {
        if (p->val <= value) {
            if (list_length(new_list) == 0) {
                new_list->front = newd_list->back = p;
                p1 = new_list->back;
            } else {
                new_list->back = p;
                p1->next = p;
                p1 = new_list->back;
            }
        } else {
            if (lst->front->val <= value) {
                lst->front = lst->back = p;
                p2 = lst->back;
            } else {
                lst->back = p;
                p2->next = p;
                p2 = lst->back;
            }
        }
        p = p->next;
    }
    return new_list;
}

CodePudding user response：

The next member of a back node of either "new" list is not always being set to NULL, instead still pointing to an old node.

In [4, 9, 2, 4, 8, 12, 7, 3] becoming [9, 8, 12, 7, 3] and [4, 2, 4, 3] we can see what should be the last node of the first list, 7, still points to its old next member, 3.

This happens because p = p->next; needs p to retain its next member through the prior body of the loop, relying on some subsequent iteration to overwrite that information (when accessed as a back node).

Another way of thinking about it: One of the lists is always implicitly NULL terminated, since some node had to be the end of the original list. The other list points into this NULL terminated list somewhere.

[9, 8, 12, 7, _]                    
           |
           V
 [4, 2, 4, 3]

An easier way to reason about this is to first create a function that adds nodes to a list.

void append(LIST *list, NODE *node) {
    if (list->front) 
        list->back->next = node;
    else                      
        list->front = node;
    
    list->back = node;
}

The filter function then resets the existing list, after taking the front node.

For each node, we save the next value for the following iteration, and then reset it to NULL, for the case when it is the last node to be added to a list.

Then it is just matter of adding it to the correct list.

LIST *filter(LIST *lst, int value) { 
    LIST *returned_list = lst_create();
    NODE *node = lst->front; 
    lst->front = ls->back = NULL;
    
    for (NODE *temp; node; node = temp) {
        temp = node->next;
        
        node->next = NULL;
                                    
        if (node->value <= value)   
            append(returned_list, node);
        else
            append(lst, node);
    }                                            
    
    return returned_list;
}