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?

Answer 1

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

Answer 2

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?

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.