CODEWITHSUNDEEP
cpointerslinked-list
user18129885
user18129885

Reputation:

How to split a linked list with a cutting value?

I successfully implemented a function but with a minor bug I can't figure out. The function filter() takes in a list. It is expected to put all elements below a value into a new list.

LIST *filter(LIST *lst, int value) {
    LIST *new_list = createlist();
    NODE *p = lst->front;
    NODE *p1 = NULL;
    NODE *p2 = NULL;
    while (p != NULL) {
        if (p->val <= value) {
            if (lengthlist(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;
}

Upvotes: 0

Views: 137

Answers (1)

Oka
Oka

Reputation: 26375

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

Upvotes: 1

Related Questions