c++ - 比较链表，C++，顺序相同但可以不同

Question

假设我们得到了函数定义

bool sameValsOrder(节点*p,节点*q)

我们必须编写一个函数来比较 2 个链表，如果它们具有相同的顺序则返回 true 否则返回 false [77777] 和 [77] -> 真

[1234567] 和 [1234555567] -> 真

bool sameValsOrder (node *p , node *q)
{
     if ( q==NULL && p==NULL)
        return true;
     else if ((q=NULL && p != NULL)|| (p=NULL && q!= NULL))
         return false;
     else if ( q != NULL && p != NULL)
           while ( q != 0 && p != 0)
            {
                if (p->data != q->data)
                    {
                        return false;
                        break;
                    }
                else 
                    {
                  p= p-> next ;
                  q= q-> next;
                    } 
            }
             return true;
    }

上面的代码是我的答案，但我意识到了一些事情。我是否需要在 while 循环中添加更多 if 语句，以便 [77777] 和 [7] 的链接列表应该返回 true，因为它们的顺序相同，只是更少。

Answer 1

根据您所写的内容，您实际上并不关心这些值，但如果列表已排序，您想要返回 true 吗？看起来您只需要遍历列表中的每个值。只要 NEXT 值不小于 PREVIOUS 值，就继续遍历列表。如果到达末尾，则返回 true，因为列表是有序的。如果在任何时候您遇到一个小于任何先前值的值，那么就在那里返回 false。

#include <iostream>

using namespace std;

class node{
public:
    node(){next = NULL;}
    int data;
    node * next;
};
class myList{
public:
    myList(){pRoot = NULL;}
    void add(int data);
    node * pRoot;
};
bool sameValsOrder (node *p , node *q)
{
     if ( q==NULL && p==NULL) // If both lists are empty
        return true;
     else if ((q==NULL && p != NULL)|| (p==NULL && q!= NULL)) // One list is empty and the other is not
         return false;
     else if ( q != NULL && p != NULL) //Both lists contain values we must check
     {      
         int temp; //I am going to assume a singly linked list (no access to previous value), need this to hold previous value
         temp = p->data; 
         while (p->next != NULL) //The list still contains elements
         {
            if (p->next->data < temp) //The value in the current node is LESS than our temp, then list is out of order so return false
                return false;
            else { //Otherwise move to the next node
                temp = p->data;
                p = p->next;
            }
         }
         temp = q->data; //Reset temp for q
         //Do the same thing for q
         while (q->next != NULL) //The list still contains elements
         {
            if (q->next->data < temp) //The value in the current node is LESS than our temp, then list is out of order so return false
                return false;
            else { //Otherwise move to the next node
                temp = q->data;
                q = q->next;
            }
         }
     }
     return true; //If we are this are then both lists should be ordered
}
int main()
{
    myList * p = new myList();
    myList * q = new myList();
    p->add(7);
    p->add(6);
    p->add(5);
    p->add(4);
    p->add(3);
    p->add(2);
    p->add(1);

    q->add(7);
    q->add(6);
    q->add(5);
    q->add(5);
    q->add(5);
    q->add(5);
    q->add(4);
    q->add(3);
    q->add(2);
    q->add(1);
    cout << sameValsOrder (p->pRoot, q->pRoot) << endl;
    return 0;
}
void myList::add(int data)
{
    node * nodeToAdd = new node();
    nodeToAdd->data = data;
    if(pRoot == NULL) //List is empty
    {
        pRoot = nodeToAdd;
        pRoot->next = NULL;
    }
    else //List not empty insert new node at beginning
    {
        nodeToAdd->next = pRoot;
        pRoot = nodeToAdd;
    }
}