我有一个几乎排序的链表，其中包含至少两个元素，仅不同，只有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;
}
我应该在其中更改什么才能正常工作？
这并不能直接回答您的问题，因为它目前是制定的：
我应该在其中更改什么(
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::is_sorted_untilwithstd::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
下面是一些经过调试(但实际上没有改进(的代码版本：
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 是乱序的吗？
这是一个更简单的解决方案。只有一个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;
这是一个开始。下一步是前进此指针以指向链接列表中所有剩余元素的next。因此，我们最终得到如下所示的内容：
for (node **p=&head; *p; p=&(*p)->next)
{
}
在这个for循环的主体中，表达式 "*p" 在逻辑上等价于第一个使用普通指针的简单循环中的普通p。
花点时间让你的大脑围绕这个循环，在你确切地了解它是如何工作的之前，不要继续前进。
. . .
现在，回到我最初的答案，你应该能够弄清楚它是如何工作的。碰巧的是，当我写我的答案时，我觉得使用while循环，但它可能只是这个精确的for循环。
使用 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);
}
}
演示