如何从几乎已排序的链表中分离出错位的元素？

Question

我是一个几乎排过序的链表，至少包含两个元素，这些元素都是不同的，只有1个元素不在它应该在的位置上。以下是一些示例：

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

结构体如下所示：

struct node {node * next; int val;}

这是我的detach函数（并不总是有效）：

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

我需要更改哪些内容才能使它正常工作？

- Philip Moreira

---

你需要改变整个算法。这种问题的正确解决方案应该只有大约六行代码。恰好一个 while 语句。恰好一个 if 语句。没有任何类似额外的 prev 指针。应该只有一个指针。如果你想出的任何东西有更多的 while 或 if 语句，或者使用了多个指针变量（除了头指针，你称之为 l），那么它就是错误的。 - Sam Varshavchik

@Jarod42 is_sorted_until是什么？ - Philip Moreira

@tadman：我不明白通过引用传递指针有什么不好的。对于外层来说，这基本上是一个风格问题，而且你也不能通过引用传递引用... - Davis Herring

可能是一个哲学问题，但在列表 {10, 25, 20, 30} 中，是 20 还是 25 次序错误？ 答案：20 是次序错误的，因为它不符合升序排列。 - paxdiablo

@tadman：关键是引用无法重新绑定，因此您需要一个指针来获得该行为。另外，“C++方式”改变参数的方法是接受对其的引用。我认为将它们组合起来得到T*&没有任何矛盾（或混乱的思维）。 - Davis Herring

Answer 1

这并没有直接回答你当前所提出的问题：

我应该在它（detach）中改变什么才能使它正确工作？

更多的是回答了“我应该如何改变它以使其更好”这个问题。然而，根据您的目标，您可能会发现它很有用。

C++ 中最佳实践是使用标准容器和算法，而不是自己编写容器或使用原始循环，因为它们经过了非常完善的测试，并且可以清晰地表达读者的意图（请参见 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

或者，您可以使用在C++11之前就可用的双向链接 std::list。区别在于，std::list::erase() 接受要删除的元素的迭代器，因此在这里使用带有 std::less<int> 的 std::is_sorted_until 更加适当：

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

- Dev Null

Answer 2

这是您的代码的某种调试版本（但实际上并未改进）:

struct node {node * next; int val;};

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)
        {
          if(prev->val>first->val)
          {
              node *removed=first;
              prev->next->next=removed->next;

              return removed;
          }
          else
          {
              node *removed=prev->next;
              prev->next=removed->next;

              return removed;
          }
        }

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

    return NULL;
}

您的测试代码片段在此链接中。

至于提出更好的解决方案，请您先澄清一下具体的要求：不清楚这是否是一个任务，您是否必须使用数据结构中的节点或者使用detach方法，还有就是回答paxdiablo的“哲学问题”：

“在列表{10，25，20，30}中，20或25是否是排序错误？”

- isp-zax

Answer 3

这是一个更简单的解决方案。只需要一个while循环和一个if语句。

node *detach(node *&l)
{
    node **p=&l;

    while ( (*p) && (*p)->next)
    {
        if ( (*p)->val > (*p)->next->val)
        {
            node *q=(*p)->next;

            (*p)->next=(*p)->next->next;

            return q;
        }

        p= &(*p)->next;
    }
    return NULL;
}

现在，先把这个问题解决了，我想我会简单解释一下它的工作原理。

让我们从遍历链表的基本循环开始看起：

node *p;

for (p=head; p; p=p->next)
{
    ;
}

这很简单。您需要携带一个指针，并将其推进到列表中的每个元素。这是每本教科书中的第一个示例。

现在，让我们退一步。假设您不是携带指向每个节点的指针，而是携带指向该指针的指针？

我是指：链表中每个元素的指针来自两个地方之一：要么是head指针，要么是前一个节点的next指针。

因此，让我们从指向head的指针开始我们的探险：

node **p=&head;

这是一个开始。下一步是将指针前进，使其指向链接列表中所有剩余元素的下一个。因此，我们最终得到类似于以下内容的东西：

for (node **p=&head; *p; p=&(*p)->next)
{
}

在这个for循环的主体中，表达式“*p”在逻辑上等同于使用普通指针的第一个简单循环中的plain p。

花一些时间来理解这个循环，直到你完全理解它的工作原理为止。

现在回到我的最初答案，你应该能够弄清楚它是如何工作的了。恰好当我写我的答案时，我觉得使用while循环，但它可以简单地改为这个for循环。

- Sam Varshavchik

Answer 4

使用 STL，您可以这样做：

int detach(std::list<int>& l)
{
    if (l.size() < 2) {
        throw std::runtime_error("too short list");
    }
    auto it = std::is_sorted_until(l.begin(), l.end());
    if (it == l.end()) {
        throw std::runtime_error("already sorted list");
    }
    if (!std::is_sorted(it, l.end())) {
        throw std::runtime_error("not 'partially' sorted list");
    }
    if (std::prev(it) == l.begin() || *it < *std::prev(it, 2)) {
//  if (std::next(it) != l.end() && !(*std::next(it) < *std::prev(it))) {
        auto res = *it;
        l.erase(it);
        return res;
    } else {
        auto res = *std::prev(it);
        l.erase(std::prev(it));
        return res;
    }
}

演示 演示

这段代码（根据你的结构）的翻译如上所示：

bool is_sorted(const node* n) {
    const node* cur = n;
    const node* next = cur->next;

    while (next != nullptr && cur->val < next->val) {
        cur = next;
        next = next->next;
    }   
    return next == nullptr; 
}

node* extract(node*& root, node* prev, node* n)
{
    if (prev == nullptr)
    {
        if (root == nullptr) {
            return nullptr;   
        }
        root = n->next;
        n->next = nullptr;
        return n;
    }
    prev->next = prev->next->next;
    n->next = nullptr;
    return n;
}

node* detach(node*& root)
{
    if (root == nullptr || root->next == nullptr) {
        throw std::runtime_error("too short list");
    }
    node* prev = nullptr;
    node* cur = root;
    node* next = cur->next;

    while (next != nullptr && cur->val < next->val) {
        prev = cur;
        cur = next;
        next = next->next;
    }
    if (next == nullptr) {
        throw std::runtime_error("already sorted list");
    }
    if (!is_sorted(it, l.end())) {
        throw std::runtime_error("not 'partially' sorted list");
    }
    if (next->next == nullptr || next->next->val < cur->val) {
        return extract(root, prev, cur);
    } else {
        return extract(root, cur, next);
    }
}

演示

- Jarod42