How do I code a function to test if a linked list is sorted

Question

I looked at other posts and didnt find a great solution for my inquiry. I don't want to actually sort the linked list I want to see if its sorted or not. I have a linked list question in c++. I am asked to code a function given a linked list definition to see if its sorted.

Implement the function isSorted – it returns true if the values in the linked list are sorted in increasing order. (The linked list is composed of integers).

given the following sturct:

struct ListNode
   {
      double value;           // The value in this node
      struct ListNode *next;  // To point to the next node
   };

Sample data: Return from isSorted
1 -> 3 -> 7 True
4 -> 2 -> 7 False
() True // Empty List.
3 True
1-> 5 -> 7 -> 2 False

I have something like this.

bool NumberList::isSorted() const
{
   ListNode *nodePtr;  // To move through the list
   nodePtr = head;

   while (nodePtr)
   {
      if(nodePtr->value <= nodePtr->value+1)
         nodePtr = nodePtr->next;
      else 
         return false;

       return true;
   }
}

I'm not sure if i'm doing this right, I need help. Thank you.

Your `return true;` should be outside of the loop, not inside it. — wolfPack88, Dec 22 '14 at 18:49
@DieterLücking there isn't a need to be rude. I was having a hard time with the logic that is why I posted the question. — Elizabeth, Dec 22 '14 at 19:03

score 2 · Answer 1 · answered Dec 22 '14 at 20:02

Maybe this will work...

bool NumberList::isSorted() const
{
    ListNode *nodePtr;
    nodePtr = head;
    double d;

    if (!nodePtr) return true; // Empty list

    // Save value of current node
    d = nodePtr->value;

    // Point to next node
    nodePtr = nodePtr->next;

    while (nodePtr)
    {
        if(d > nodePtr->value) return false; // Not sorted

        // Save value of current node
        d = nodePtr->value;

        // Point to next node
        nodePtr = nodePtr->next;
    }

    return true;
}

Cheers and hth. - Alf · Accepted Answer · 2014-12-22T18:54:57.540

1

If the list is sorted in ascending order, then for the comparison function you're using each node has greater or equal value to the previous one. I.e. the values are never decreasing. Just iterate through the nodes and check that.

Note: the condition you have shown,

nodePtr->value <= nodePtr->value+1

does not check anything reasonable: it checks whether a value is less than or equal to that value plus 1.

One idea for a more reasonable condition is to compare nodePtr->value to the previous node's value. To do that easily, you need to have stored the previous node's value (or a pointer to the previous node) in the previous iteration. In some variable.

edited Dec 22 '14 at 18:54

answered Dec 22 '14 at 18:49

Cheers and hth. - Alf

142,714
15
209
331

Yes, I'm being asked to test if my list is sorted in ascending order. i listed the given sample data - it is true in the instances specified and false only if the values are not sorted in ascending order. I understand your statement, how do i fix it to check for the given options. – Elizabeth Dec 22 '14 at 18:51
SO based on your suggestion I would declare a value set it equal to nodePtr->value. Then iterate through my loop, if my following value is greater then the preceding set temp value. I'm ok. I would have to update my temp value with each iteration? – Elizabeth Dec 22 '14 at 18:57
Note that as well as testing that the visited nodes compare in ascending order, it's also important to test that the node *count* matches your expectations, in case your linked list code has somehow left off a node or broken a `previous` or `next` link inadvertently. – Matt Coubrough Dec 22 '14 at 18:58

score 0 · Answer 3 · edited Jan 29 '21 at 07:18

#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    struct node* next;
};
void insert(struct node* p,int x)
{
    struct node* q=new node;
    while(p->next!=NULL)
    {
        p=p->next;
    }
    p->next=q;
    q->data=x;
    q->next=0;

}
void printlist(struct node* p)
{
    while(p)
    {
        cout<<p->data<<" ";
        p=p->next;
    }
}
bool ifsorted(struct node* p)
{
    while(p->next!=NULL)
    {
        if(p->data>p->next->data)
            return false;
        p=p->next;


    }
    return true;

}
int main()
{
   struct node* head=new node;
   struct node* second=new node;
   struct node* third=new node;
   head->data=1;
   head->next=second;
   second->data=2;
   second->next=third;
   third->data=3;
   third->next=NULL;
   insert(head,4);
   insert(head,56);
   insert(head,100);
   printlist(head);
   ifsorted(head)?cout<<"Sorted":cout<<"Not sorted";

}

Try to use comments to guide and provide additional information. — MCL, Jan 29 '21 at 06:43

How do I code a function to test if a linked list is sorted

3 Answers3

Linked