Compare two linked list of integers to verify whether they are identical. The linked lists are identical if they have the same size and same elements in same order.

Your method will have two parameters - pointers to the head of the two linked lists to be compared.

Your method should return an integer. It should return 1 if the lists are identical and 0 otherwise.

Firstly we need to figure out what "identical" exactly means. It means:

1. The length of both the linked list have to be exactly same.
2. The data of each node of the first linked list has to be exactly equal to the data of the corresponding node in the second linked list, i.e. A's first node data has to be equal to B's first node data, A's second node data has to be equal to B's second node data and so on.

So what essentially needs to be done is to traverse both the linked lists at the same time and compare if both the node's data are same or not. If they are unequal even at one position, we can straight away conclude that the lists given are not identical.

How can we traverse both the linked list at the same time? Well, in the same way that we traverse for one linked list. Just iterate in a while loop with the condition that the list is not yet completed, i.e. while(A != NULL && B != NULL) read as "while A is not yet null (not yet finished) and B is not yet null (not yet finished)". and update the nodes of both lists to point to their next elements at the end of the body of the loop. Therefore, provided that the length of both the linked are same, we can compare them as:

while (A != NULL && B != NULL) { 
    //while both the lists still have nodes left
        if (A->data != B->data) { 
       //If both the data are not equal then the lists are not identical -
       //so directly return 0.
		    return 0;
	    }
           //Otherwise just update the pointers to point to the next -
           //element of both lists.
	    A = A->next; 
	    B = B->next;
    }

Now, the final thing to check is if the lists length are same or not. If the length of both the lists were same, then after the execution of the above while loop, both A and B must have pointed to NULL at the same time.

So we just need to check if both point to NULL after the execution of the while loop. If yes, then both lists are of the same size, and hence identical and we can return 1, otherwise we return 0.

editorial written by phantom11

/*
  Compare two linked lists A and B
  Return 1 if they are identical and 0 if they are not. 
  Node is defined as 
  struct Node
  {
     int data;
     struct Node *next;
  }
*/
int CompareLists(Node *A,Node* B) {
    while (A != NULL && B != NULL) { 
    //while both the lists still have nodes left
        if (A->data != B->data) { 
        //If both the data are not equal then the lists are not identical -
        //so directly return 0.
		    return 0;
	    }
           //Otherwise just update the pointers to point to the next -
           //element of both lists.
	    A = A->next; 
	    B = B->next;
    }
    //Now check if length of both lists are same or not.
    //If both A and B point to NULL now, that means both had equal number-
    //of elements, so they were identical.
    if(A == NULL && B == NULL) { 
        return 1;
    }
    else {
        return 0;
    }
}

featured solution by phantom11