GATE CSE
First time here? Checkout the FAQ!
x
0 votes
123 views

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.

asked in DS by (427 points)  
edited by | 123 views
$val2 = 2*val2 + p\rightarrow data;$
How ???

1 Answer

+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$

answered by Boss (9.3k points)  
edited by
Thanks for the perfect answer...
Well explained !

Related questions

0 votes
1 answer
1
asked in DS by Arnab Bhadra Loyal (4.8k points)   | 79 views
0 votes
3 answers
2
+2 votes
1 answer
3
asked in DS by thor Boss (8.7k points)   | 242 views


Top Users Aug 2017
  1. ABKUNDAN

    4658 Points

  2. Bikram

    4134 Points

  3. akash.dinkar12

    3144 Points

  4. rahul sharma 5

    2928 Points

  5. manu00x

    2682 Points

  6. makhdoom ghaya

    2390 Points

  7. just_bhavana

    2058 Points

  8. Tesla!

    1782 Points

  9. pawan kumarln

    1574 Points

  10. learner_geek

    1558 Points


24,892 questions
31,967 answers
74,213 comments
30,083 users