GATE IT 2005 | Question: 54

Question

The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure. 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 the 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;
      }
}

• A. $1, 2, 3, 4, 5, 6, 7$
• B. $2, 1, 4, 3, 6, 5, 7$
• C. $1, 3, 2, 5, 4, 7, 6$
• D. $2, 3, 4, 5, 6, 7, 1$

Comments

Redundant --> https://gateoverflow.in/485/gate2008-62

---

Good catch -- rare to see an exact copy in previous questions :)

---

$

GATE CSE 2008 | Question: 62

 

$

Answer 1

It is (B) $2, 1, 4, 3, 6, 5, 7$:

As, $p$ and $q$ are swapping each other where $q$ is $p \rightarrow next $ all the time. 

Comments

Yes. Thats what it is doing :)

Answer 2

struct node {int value; struct node *next;);
void rearrange (struct node *list) {
    struct node *p, *q;
    int temp;
    if (!list || !list -> next) return; // just check 1st time two adjacent node are there or not. if not program is finish . for example take one node or 0 node in linked list output will be same as input.
    p = list; q = list -> next; two pointer to point two adjacent node p point first node  q point second node which is adjacent to first.
    while (q) this will check always two adjacent present or not like if at one point only p point some node and q point to null then loop stop running.
      { 
        1.temp = p -> value;
        2.p -> value = q -> value;
        3.q -> value = temp; till here swapping done via temp variable.
        4.p = q -> next; just point next node
        5.q = p ? p -> next : 0; this will one if p point to some node then q point to its next node. if p point to null then q also point 0.
      }
}

Finally while loop take care two node present to swap .

if one node present at any time between running of program then while loop terminate.

Comments

for this 

q = p ? p -> next : 0;

which one is correct (1) or (2)  ??

---

1st is correct.