时间戳

首页 > 解决方案 > 从 LinkedList 中清除序列

c++ - 从 LinkedList 中清除序列

问题描述

编辑 我必须从 LinkedList 序列中删除它们的总和等于 5。

例如对于这个链接列表：{3,2, 1, 4, 10,3,3,2,1}我得到 {10, 3, 3, 2, 1}。我真的不知道为什么会这样，它也应该删除 3,2 ，但它没有。

void LinkedList::cleanFive(LinkedList& list)
{
head = list.GetHead();

Node* end = head;
Node* headd = head;
Node* flag = head;
Node* curr = head;

int sum = 0;


while (end) {
    sum += end->data;

    if (sum < 5) {
        end = end->next;
    }
    if (sum == 5) {
        end = end->next;
        headd = end;
        flag = headd;
        head = flag;
        sum = 0;
    }
    if (sum > 5) {
        flag = head;
        curr = end;
        end = end->next;
        sum = 0;
    }
}

}

标签： c++

解决方案

curr = head;
end = head;
currprev = nullptr;

std::vector<Node*> flag;
while(end) {
     sum += end->data;
     if (sum < 5) {
         flag.push_back(end);
         end = end->next;
     }

     if (sum > 5) {
         currprev = curr;
         curr = curr->next;
         end = curr;
         sum = 0;
         empty_flag()
     }

     if (sum == 5) {
         curr = end->next;
         end = curr;
         sum = 0;
         delete_nodes_from_flag_from_linked_list()
         empty_flag()
     }

}

这是一个可能的解决方案。在这种情况下，flag 是一个节点向量，直到总和被证明为 5 或更大为 5。使用 flag 需要进行两个操作： empy_flag() - 从向量中删除所有条目和 delete_nodes_from_flag_from_linked_list( ) - 从链表中删除标志中的元素。

delete_nodes_from_flag_from_linked_list() 的代码应如下所示：

auto it = flag.end();
it--;
Node* last = *it;

if (currprev)
    currprev->next = last->next;
else
    head = last->next

for (auto f : flag) 
    delete f;

其中 currprev 是 curr 之前的元素。您必须从一开始就跟踪此元素，除非您的链表元素保留指向先前元素的指针。我正在从上面更新代码。head 是列表的开头。

推荐阅读