comparing linked list , C++ , same order but can be different seize

Let's say we are given the function definition

bool sameValsOrder(node *p , node *q)

We have to write a function to compare the 2 linked list if they have the same order it returns true else false [77777] and [77] -> true

[1234567] and [1234555567] -> true

bool sameValsOrder (node *p , node *q)
{
     if开发者_Python百科 ( 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;
    }

The above code is my answer but I realized something. Do I need to add more if statement inside the while loop such that a link list of [77777] and [7] should return true since its the same order just less.

According to what you have written you don't actually care about the values but you want to return true if the list is ordered? It seems like you just need to go through each value in the list. As long as the NEXT value is NOT LESS than the PREVIOUS value keep going through the list. If you reach the end, then return true because the list is in order. If, at any point you come across a value that is less than any previous value then just return false right there.

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

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

this is wrong you are returning false when it is not same but as the size of p and q can be different [1112] [12] will return false which it shouldnt

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

Basically you should move forward in the first linked list only when the values don't match other wise traverse the second list till it matches.

The OP has indicated in comments that he wants to consider 'runs' of nodes with the same data as being matched even if those runs have a difference length in the 2 lists. That simplifies to when (q->data == p->data) then skip nodes that comprise a run.

Here's some pseudocode; a C implementation is really not any more complex (though it might be several more lines):

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 Implementation:

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