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

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

这并不直接回答您的问题,因为它目前已制定:

我应该改变什么在它(detach)才能正常工作？

这更像是"如何改变它以使其变得更好"的答案.但是,根据您的目标,您可能会发现它很有用.

在C++中的最佳实践是使用标准容器和算法,而不是推出自己的容器或使用原始循环,因为,除其他事项外,他们是很好的测试,并清晰地表达自己的意图读者(见讲座由Sean家长对更多细节).

假设您有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

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

包含您的测试序列的工作片段位于此处

至于花一些时间提出更好的解决方案，您必须澄清一下要求是什么：不清楚这是否是一个分配并且您必须使用数据限制节点，或者如果这是您的选择并且分离方法也是如此- 如果应该是那样或你的想法。另外，你必须回答 paxdiablo 的“哲学问题”：

在列表 { 10, 25, 20, 30 } 中，20 或 25 是否乱序？