in DS recategorized by
344 views
5 votes
5 votes

Consider the following function foo() which takes the head pointer of two singly-linked lists.

struct node *foo(struct node *head1, struct node *head2)
{
    struct node *final, *temp;
    if (head1 == NULL) return head2;
    if (head2 == NULL) return head1;
    temp = foo(head1->next, head2->next);
    final = head1;
    head1 -> next = head2;
    head2 -> next = temp;
    return final;
}


What will be the final linked list returned by foo() if executed upon following linked lists?

  1. $1,2,3,4,5,7,8,9,10$
  2. $1,2,3,4,5,7,8,10,9,10$
  3. $1,2,3,4,5,8,7,10,9,10$
  4. None of these
in DS recategorized by
344 views

2 Comments

Already there are good answers below. What I want to add is these type of questions are pattern based. Once you have solved for last and second last function, you will realise what the function is doing. So no need to calculate for all the function calls. Just ensure that the same pattern is following till the beginning/end of the function call.
1
1

@neel19 agreed. It's better to understand what the code is doing, rather than dry running code each time. Saves a lot of time.

0
0

3 Answers

4 votes
4 votes

Here, in diagram -

H1,i $\implies$ head1 pointer for ith foo() call.

H2,i $\implies$ head2 pointer for ith foo() call.

Ti $\implies$ temp pointer for ith foo() call.

Fi $\implies$ final pointer for ith foo() call.

foo() call sequence – 

foo(H1,1 ; H2,1) $\implies$ foo(H1,2 ; H2,2) $\implies$ foo(H1,3 ; H2,3) $\implies$ foo(H1,4 ; H2,4) $\implies$ foo(H1,5 ; H2,5).


foo(H1,5 ; H2,5) $\implies$ Here, H2,5 is NULL. So, this function call returns H1,5.


foo(H1,4 ; H2,4) $\implies$ Here, H1,4 and H2,4 both are not NULL. T4 = H1,5 due to foo(H1,5 ; H2,5) return.

F4 = H1,4 and H1,4 points to H2,4 and H2,4 points to H1,5 (Green arrows in diagram). And this function call returns H1,4.


foo(H1,3 ; H2,3) $\implies$ Here, H1,3 and H2,3 both are not NULL. T3 = H1,4 due to foo(H1,4 ; H2,4) return.

F3 = H1,3 and H1,3 points to H2,3 and H2,3 points to H1,4 (Sky Blue arrows in diagram). And this function call returns H1,3.


foo(H1,2 ; H2,2) $\implies$ Here, H1,2 and H2,2 both are not NULL. T2 = H1,3 due to foo(H1,3 ; H2,3) return.

F2 = H1,2 and H1,2 points to H2,2 and H2,2 points to H1,3 (Orange arrows in diagram). And this function call returns H1,2.


foo(H1,1 ; H2,1) $\implies$ Here, H1,1 and H2,1 both are not NULL. T1 = H1,2 due to foo(H1,2 ; H2,2) return.

F1 = H1,1 and H1,1 points to H2,1 and H2,1 points to H1,2 (Pink arrows in diagram). And this function call returns H1,1.


After execution – 

1 → 2 → 3 → 4 → 5 → 8 → 7 → 10 → 9 → 10 → \0

Answer :- C.

3 votes
3 votes

Answer is option C 

Please dont mind with the notations that i used in this question

0 votes
0 votes

there is no “rec ” variable defined in function but used in 2nd last line thats why i have marked option D .

2 Comments

Bro where is rec in the question??
0
0
That has been updated by sachin sir
0
0
Answer:

Related questions