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

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.

Answer 1

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

Answer 2

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.