如何拆分具有切割值的链表？

Question

我成功地实现了一个功能，但有一个我无法弄清楚的小错误。函数 filter() 接受一个列表。希望将某个值下的所有元素放入一个新的列表中。

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

Answer 1

任一“新”列表的后节点的 next 成员并不总是设置为 NULL，而是仍然指向旧节点。

在[4, 9, 2, 4, 8, 12, 7, 3]变为[9, 8, 12, 7, 3]和[4, 2, 4, 3]中我们可以看到第一个列表的最后一个节点7仍然指向它的旧next 成员，3.

发生这种情况是因为 p = p->next; 需要 p 通过循环的先前主体保留其 next 成员，依赖于一些后续迭代来覆盖该信息（当作为back节点）。

另一种思考方式：其中一个列表总是隐式地 NULL 终止，因为某些节点必须是原始列表的末尾。另一个列表指向此 NULL 某处终止列表。

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

一个更简单的推理方法是首先创建一个将节点添加到列表的函数。

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

过滤器函数然后在获取前节点后重置现有列表。

对于每个节点，我们为下一次迭代保存 next 值，然后将其重置为 NULL，以防它是要添加到列表中的最后一个节点。

然后只需将它添加到正确的列表即可。

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

如何拆分具有切割值的链表？

How to split a linked list with a cutting value?

c

pointers

linked-list