c++ - 如何编写一个函数来测试链表是否已排序

Question

我查看了其他帖子，但没有为我的查询找到很好的解决方案。我不想真正对链接列表进行排序，我想看看它是否已排序。我在 C++ 中有一个链表问题。我被要求编写一个给定链表定义的函数，以查看它是否已排序。

实现函数 isSorted——如果链表中的值按递增顺序排序，则返回 true。 (链表由整数组成)。

给定以下结构:

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

示例数据:从 isSorted 返回
1 -> 3 -> 7 真
4 -> 2 -> 7 错误
() True//空列表。
3 正确
1-> 5 -> 7 -> 2 错误

我有这样的东西。

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

我不确定我这样做是否正确，我需要帮助。谢谢。

Answer 1

也许这会奏效...

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