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

Question

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

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

结构如下所示：

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

            return removed;
        }

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

    return NULL;
}

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

Answer 1

这里是你的代码的一些调试版本（但没有真正改进）：

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

您的测试序列的工作片段是 here

至于抽出一些时间来提出更好的解决方案，您必须澄清一下要求是什么：不清楚这是一项任务并且您必须使用数据结构节点，或者这是您的选择分离方法也一样——如果它应该是那样或者你的想法。此外，您必须回答 paxdiablo 的 "philosophical question"：

in the list { 10, 25, 20, 30 }, is 20 or 25 out of order?

Answer 2

这是一个更简单的解决方案。只有一个 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;
}

现在，我想我会稍微解释一下它是如何工作的。

让我们从遍历 linked 列表的基本循环开始：

node *p;

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

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

现在，让我们退后一步。假设不是携带一个指向每个节点的指针，而是携带一个指向那个指针的指针怎么样？

这是什么意思：指向 link 列表中每个元素的指针来自两个位置之一：它是 head 指针或 next 指针来自上一个节点。

那么，让我们开始我们的冒险吧，把指针指向 head:

node **p=&head;

这是一个开始。下一步是将此指针前进到指向 link 列表中所有剩余元素的 next。所以，我们最终得到的结果看起来像这样：

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

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

花点时间思考一下这个循环，在您完全理解它是如何工作之前不要继续。

。 . .

现在，回到我最初的回答，你应该能够弄清楚它是如何工作的。碰巧的是，当我写下我的答案时，我想使用 while 循环，但它可能只是这个确切的 for 循环。

Answer 3

这并不能直接回答你的问题，因为它是目前制定的：

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

这更像是对 "How should I change it to make it better" 的回答。但是，根据您的目标，您可能会发现它很有用。

C++ 中的最佳实践是使用标准容器和算法，而不是推出您自己的容器或使用原始循环，因为除其他外，它们经过了很好的测试并清楚地表达了您对 reader（有关详细信息，请参阅 a talk by Sean Parent）。

假设你有 C++11，你可以使用 std::forward_list as a singly-linked list implementation and std::adjacent_find algorithm to find the last element that is ordered correctly (std::is_sorted_until 不能与 std::forward_list 一起使用，因为它将 return 第一个元素是排序不正确 单向链表无法返回到前一个元素):

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::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

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

Demo Demo

将（对于您的结构）转换为：

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

Demo

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

How to detach misplaced element from almost sorted linked list?

c++

sorting

linked-list

list

insertion-sort