0 votes

Q)The below code returns decimal value of binary linked list

int val(struct Node *head) { struct Node *p = head; int val2= 0; while (p!= NULL) { XYZ;//fill the contents of XYZ p = p→next; } return val2; }

What is XYZ in above code ? Please provide a sound explaination too.

3 votes

Best answer

In the given linked list we traverse starting from Head and ending at tail.

If it would be an array,then we simply start from $Ar\left [ n \right ]\, to\, Ar\left [ 1 \right ]$ and each time we would multiply with $2^{i}\, \, ,i=0,1,2\cdots \left ( n-1 \right )$,Like this

for(j=n,i=0;j>=1 & i<n;j--,i++) { res=pow(2,i)*ar[j]+res; } printf("Equivalent value =%d",res);

But as in Linked list according to your question ,we cannot traverse from tail to head as you have not provided the length of linked list.so starting from head it can be done as-:

res=(res*2)+p->data;

$OR$

res=(res<<1)+p->data

which is your $XYZ$

Example -:

$2*0+1\left ( p\rightarrow data\left ( 100 \right ) \right )=1$

$2*1+0\left ( p\rightarrow data\left ( 200 \right ) \right )=2$

$2*2+1\left ( p\rightarrow data\left ( 300 \right ) \right )=5$

$2*5+1\left ( p\rightarrow data\left ( 400 \right ) \right )=11$