比较链表，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;
    }
}

Answer 2

 while ( q != 0 && p != 0)
        {
            if (p->data != q->data)
                    return false;
                    break;
            else 
              p= p-> next ;
              q= q-> next;
        }

这是错误的，当它不相同，但p和q的大小可能不同时，你会返回false[1112][12]将返回false，它不应该

Answer 3

while(q!=NULL || p!=NULL)
{    
    if(q->data==p->data)    
    { 
        p=p->next;
        break;
    }
    else(q->data <  p->data)
    q=q->next;
}

基本上，只有当值不匹配时，才应该在第一个链表中向前移动。其他方式是遍历第二个列表，直到它匹配为止。

Answer 4

OP在评论中表示，他希望将具有相同数据的节点的"运行"视为匹配，即使这些运行在两个列表中的长度不同。这简化为(q->data == p->data)跳过包含运行的节点。

这里有一些伪代码；C的实现实际上并不复杂(尽管它可能还有几行(：

bool sameValsOrder (node *p , node *q)
{
    while not at the end of either list, and the current nodes are the same {
        skip run in q, taking care to deal with the NULL at the end of the list
        skip run in p, taking care to deal with the NULL at the end of the list
    }
    if we've reached the end of both lists, they are equivalent
}

C实施：

bool sameValsOrder (node *p , node *q)
{
    while (q && p && (q->data == p->data)) {
        /* find next different node in each list (ie., skip runs) */
        int tmp = q->data;  /* or whatever type `data` is */
        while (q && (q->data == tmp)) {
            q = q->next;
        }
        while (p && (p->data == tmp)) {
            p = p->next;
        }
    }
    /*
     * we've either reached the end of one or both lists, 
     *  or have found a `data` difference
     */
    if (p == q) {
        /* should happen only when `q` and `p` are NULL */
        assert(q == NULL);
        assert(p == NULL);
        /* we've reached the end of both lists, so they're 'equivalent' */
        return true;
    }
    return false;
}