c++ - 如何从几乎已排序的链表中分离放错位置的元素？

Question

我有一个几乎排序的链表，它至少包含两个元素，只有不同的元素，只有 1 元素不在它的位置。一些例子:

28 (144) 44 52 60
60 68 76 84 (65) 100

结构看起来像这样:

结构节点{node * next;整数值；

这是我的分离函数(并不总是有效):

node *detach(node *&l)
{
    if(l->val>l->next->val)
    {
        node *removed=l;
        l=l->next;

        return removed;
    }

    node *first=l->next->next;
    node *prev=l;

    while(first!=NULL)
    {
        if(prev->next->val>first->val)
        {
            node *removed=prev->next;
            prev->next=removed->next;

            return removed;
        }

        prev=prev->next;
        first=first->next;
    }

    return NULL;
}

我应该对其进行哪些更改才能正常工作？

Answer 1

这并不能直接回答您目前提出的问题:

What should I change in it (detach) to work correctly?

这更像是对“我应该如何改变它以使其变得更好”的回答。但是，根据您的目标，您可能会发现它很有用。

C++ 中的最佳实践是使用标准容器和算法，而不是推出您自己的容器或使用原始循环，因为除其他外，它们经过了很好的测试并向读者清楚地表达了您的意图(参见 a talk by Sean Parent了解更多详情)。

假设你有 C++11，你可以使用 std::forward_list 作为单链表实现和 std::adjacent_find 查找最后一个正确排序的元素的算法( std::is_sorted_until 不能与std::forward_list 一起使用，因为它会返回第一个排序不正确的元素，您可以不要返回到单链表的前一个元素):

std::forward_list<int> list = {60, 68, 76, 84, 65, 100};
auto last_sorted = std::adjacent_find(list.cbegin(), list.cend(), std::greater_equal<int>{});
// use last_sorted here
list.erase_after(last_sorted); // delete the not-in-place-element after you are done

或者，您可以使用双向链接 std::list在 C++11 之前可用。不同之处在于 std::list::erase()接受指向要删除的元素的迭代器，因此 std::is_sorted_until与 std::less<int>在这里更合适:

std::list<int> list = {60, 68, 76, 84, 65, 100};
auto last_sorted = std::is_sorted_until(list.cbegin(), list.cend(), std::less<int>{});
// use last_sorted here
list.erase(last_sorted); // delete the not-in-place-element after you are done