518 views
2 votes
2 votes

The following C function takes a singly-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 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;
        q = p ? p -> next : 0;
    }
}
  1. 2,1,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

1 Answer

Best answer
4 votes
4 votes

Compare both the programs below with the marker =>

A). 

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;
      }
}

Clearly, swapping is being done so output for this is 2, 1 ,4 ,3, 6 ,5, 7

B). 

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;
        q = p ? p -> next : 0;
    }
}

Clearly, again swapping is being done, but in a different way. Output is 2,3,4,5,6,7,1 .

selected by
Answer:

Related questions

4 votes
4 votes
2 answers
2
Arjun asked Oct 10, 2016
1,407 views
For a singly linked list where each node has a pointer to a data array as well as a next pointer, what would be the worst case time complexity to delete an intermediate n...
4 votes
4 votes
1 answer
3
Arjun asked Oct 10, 2016
727 views
In a Network where bytes are continuously being transferred, it is required to identify the most frequently transferred byte. What would be an appropriate data structure ...