How to detach misplaced element from almost sorted linked list?

Question

I have an almost sorted linked list containing at least two elements, distinct only, with only 1 element not in it's place. Some examples:

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

The struct looks like this:

struct node {node * next; int val;}

Here's my detach function (not always working):

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

What should I change in it to work correctly?

Calesta

You need to change the entire algorithm. The correct solution to this kind of a problem should only be, about, six lines of code. Exactly one while statement. Exactly one if statement. Nothing remotely like this extra prev pointer. Should only be one pointer. If whatever you come up with has more while or if statements, or uses more than one pointer variable (except for the head pointer, which you call l), it'll be wrong. – Splendiferous

Seeing node *&l is a sign something very odd is going on here. When using pointers it's usually node** l, and when using references there's no need for pointers at all. – Forrestforrester

Element to remove is one of is_sorted_until or previous one. – Camelopardus

@Camelopardus What is is_sorted_until? – Calesta

std::is_sorted_until (even if not directly applicable as you have an own hand written list without iterator). – Camelopardus

@tadman: I fail to see what is undesirable about passing a pointer by reference. The choice for the outer layer is basically a point of style, and it’s not like you can pass a reference by reference… – Leatherjacket

@SamVarshavchik I am just a beginner hence my code is the best I can do. Could you spare some time to implement a good solution? – Calesta

@DavisHerring Why would you never need to pass a reference by reference? Convention holds you pass references or pointers to pointers. This mixed approach is just plain odd. Newer C++ code obviously steers towards a references only design, older C++ code tends towards more C-style pointer slinging. The real question here is why this is a stand-alone function and not a class function. – Forrestforrester

May be a philosophical question but, in the list { 10, 25, 20, 30 }, is 20 or 25 out of order? – Adaptable

If you have 1 6 4 10, do you remove 4 and get 1 6 10 which is valid or you remove 6 and get 1 4 10which is also valid? If you have 1 6 4 5, then obviously, 6 need to be removed. – Androgen

@tadman: The point is that references cannot be rebound, so you need a pointer to get that behavior. Separately, the “C++ way” to mutate an argument is to accept a reference to it. I see no contradiction (or confused thinking) in composing these to get T*&. – Leatherjacket

@SamVarshavchik You need at least 2 if because once you find an out-of-order item, you need to decide if that item or the previous one need to be removed (see my examples in a previous comment) – Androgen

@PhilipMoreira do you absolutely have to use your own implementation of a singly-linked list or you are fine with using standard containers? – Raman

Answer 1

Here is somewhat debugged (but not improved really) version of your code:

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

Working snippet with your test sequences is here

As for sparing some time to propose a better solution, you'd have to clarify a bit what requirements are: not clear if this is an assignment and you HAVE to use the data stricture node or if this is your choice and same about detach method - if it should be that way or your idea. Also, you'd have to answer paxdiablo's "philosophical question":

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

Gause

Answer 2

This doesn't directly answer your question as it is currently formulated:

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

This is more of an answer to "How should I change it to make it better". However depending on your goals you might find it useful.

The best practice in C++ is to use standard containers and algorithms instead of rolling out your own containers or using raw loops because, among other things, they are very well tested and express your intent clearly for the reader (see a talk by Sean Parent for more details).

Assuming that you have C++11, you could use 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 wouldn't work with std::forward_list because it will return the first element that is ordered incorrectly and you can't go back to the previous element with a singly-linked 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

Alternatively, you could use doubly-linked std::list that is available before C++11. The difference is that std::list::erase() accepts an iterator to the element to be deleted, hence std::is_sorted_until with std::less<int> is more appropriate here:

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

Raman

Answer 3

This is a much simpler solution. Just one while loop, and one if statement.

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

Now, with that out of the way, I think I'll just add a little bit of an explanation of how this works.

Let's start by looking at the basic loop for traversing a linked list:

node *p;

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

That's as simple as it gets. You carry a pointer, and advance it to each element in the list. This is the first example in every textbook.

Now, let's take one step back. Suppose that instead of carrying a pointer to each node, how about carrying a pointer to that pointer?

What do I mean by that: a pointer to each element in the link list comes from one of two places: it's either the head pointer, or the next pointer from the previous node.

So, let's begin our adventure by taking the pointer to the head:

node **p=&head;

That's a start. The next step is to advance this pointer to point to the next for all remaining elements in the link list. So, we end up with something that looks like this:

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

Inside the body of this for loop, the expression "*p" is logically equivalent to plain p in the first, simple loop that uses a plain pointer.

Take a few moments to wrap you brain around this loop, and do not proceed further until you understand exactly how it works.

. . .

Now, go back to my initial answer, and you should be able to figure out how it works. It just so happens that when I wrote my answer I felt like using a while loop, but it could simply be this exact for loop, instead.

Splendiferous

Answer 4

With stl, you might do:

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

Which translate (for your structure) to:

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

Camelopardus