Question: problem 1 the function numdistinct to the right takes an...
Question details
PROBLEM 1: The function num_distinct to the right takes an array a[] of n integers and determines the number of distinct values in the array. This number is then returned. Examples: [5, 5, 5, 5, 5] has one distinct value. [1, 2, 3, 4, 5] has five distinct values. [1, 2, 3, 2, 1] has three distinct values. Take a few minutes to understand the logic of the function and why it works. |
int num_distinct(int a[], int n){ int i, j, ndistinct; bool is_dup; ndistinct=0; for(i=0; i<n; i++) { is_dup=false; for(j=0; j<i; j++) { if(a[j] == a[i]) is_dup = true; } if(!is_dup) ndistinct++; } return ndistinct; } |
Your job: write a linked-list version of exactly the same algorithm. A linked list is a sequence of elements just like an array after all -- i.e., a given linked list either has duplicates or it does not. Use the struct and function prototype below. |
struct node { int val; node *next; }; int num_distinct(node *lst) { } |
You will submit your code just within your homework document (i.e., you are not submitting your .cpp file). Of course, you are free and encouraged to try out your solution in a real program.