Register
Dark Mode

GO Classes Weekly Quiz 9 | Data Structures | Linked List | Question: 10

in DS recategorized by
374 views
6 votes
6 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
by
374 views

2 Comments

by
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
by

@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.

by
3 votes
3 votes

Answer is option C 

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

by
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 .

by

2 Comments

by
Bro where is rec in the question??
0
0
by
That has been updated by sachin sir
0
0
Answer:
← PreviousNext →
← Previous in categoryNext in category →

Related questions

Subscribe to GATE CSE 2023 Test Series

Subscribe to GO Classes for GATE CSE 2023

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Developed by Chun
Link Copied!