The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+19 votes
2.5k views

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers $1, 2, 3, 4, 5, 6, 7$ in the given order. What will be the contents of the list after function completes execution?

struct node {
    int value;
    struct node *next;
};

void rearrange(struct node *list) {
    struct node *p, *q;
    int temp;
    if (!list || !list -> next) return;
    p = list; q = list -> next;
    while(q) {
        temp = p -> value; p->value =  q -> value;
        q->value = temp; p = q ->next;
        q = p? p ->next : 0;
    }   
}
  1. $1, 2 ,3, 4, 5, 6, 7$
  2. $2, 1, 4 ,3, 6, 5, 7$
  3. $1, 3, 2, 5, 4, 7, 6$
  4. $2, 3, 4, 5, 6, 7, 1$
asked in DS by Veteran (59.5k points)
edited by | 2.5k views
0

3 Answers

+18 votes
Best answer

The loop is interchanging the adjacent elements of the list. But after each interchange, next interchange starts from the unchanged elements only (due to $p = q \rightarrow  next$;).

$1$st iteration $1, 2, 3, 4, 5, 6, 7$
            $\Rightarrow  2, 1, 3, 4, 5, 6, 7$

$2$nd iteration $2, 1, 4, 3, 5, 6, 7$

$3$rd iteration $2, 1, 4, 3, 6, 5, 7$

$p$ pointing to null $q$ pointing to $7$, as $p$ is false hence $q=p?$ $p  \rightarrow next$:$0$; will return  $q=0$ ending the loop

Answer is option B.

answered by Active (2.6k points)
edited by
–1
correction, p will point to 7, and q=p true, hence q = p->next = null
+1

can someone explain me this line

q = p? p ->next : 0;

After first exchange p points to q->next, so this expression should evaluate to false making q=0...but its executing p->next..why?? what am i missing? @Arjun @ManaliSikdar

+8
it is q = p, not q == p. q = p? this returns true, if p is any non-zero value.
+1
oh okay...got it.
0

how p will point to null?

p will point to 7 and q will point to NULL (q = p->next as p is a non zero value)

Edit:
Program: http://ideone.com/T0yVty

0
q = p? p ->next : 0;

Basically it is ternary operator . we can rewrite this expression in simplified form

q = (p!=NULL)? p -> next : 0;

when (p!=NULL ) true then q = p ->next will be assigned when this condition is false then q = 0 will be assigned. 

+4 votes
answered by Loyal (6.6k points)
+1
Yes, the only time when question generator algorithm went wrong :P
–1 vote
ans b)
answered by Active (5.2k points)
Answer:

Related questions



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

37,976 questions
45,471 answers
131,383 comments
48,425 users