Dark Mode

344 views

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,2,3,4,5,7,8,9,10$
- $1,2,3,4,5,7,8,10,9,10$
- $1,2,3,4,5,8,7,10,9,10$
- None of these

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

@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

4 votes

Here, in diagram -

**H1,i** $\implies$ head1 pointer for i^{th} foo() call.

**H2,i **$\implies$ head2 pointer for i^{th} foo() call.

**Ti** $\implies$ temp pointer for i^{th} foo() call.

**Fi** $\implies$ final pointer for i^{th} 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.**