Question
In C++ Write a function to compare whether two linked lists are the same. You may use function templates, or just force a particular list type (for example int). Your function should be able to handle different cases of input. For example, the lengths of two linked lists may be different. Then test your function in a main function. In the main function, you need to do the following:
(1) Build two linked lists.
(2) Display the two linked lists.
(3) Call your function to compare the two linked lists.
(4) Output the result to indicate whether they are the same or not.
Explanation / Answer
#include 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 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 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 pRoot) next = NULL; } else //List not empty insert new node at beginning { nodeToAdd->next = pRoot; pRoot = nodeToAdd; } }