The following C function takes a singly-linked list of integers as a parameter…
2005
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
Attempted by 126 students.
Show answer & explanation
Correct answer: B
Answer: 2, 1, 4, 3, 6, 5, 7
Key idea: The function swaps the values of each pair of adjacent nodes: it swaps p->value and q->value, then advances p to the node after that pair and q to the next node (the second of the next pair).
Start: 1, 2, 3, 4, 5, 6, 7
Swap first pair (nodes with values 1 and 2) -> 2, 1, 3, 4, 5, 6, 7
Advance to next pair and swap (nodes with values 3 and 4) -> 2, 1, 4, 3, 5, 6, 7
Advance to next pair and swap (nodes with values 5 and 6) -> 2, 1, 4, 3, 6, 5, 7
Now p points to the last node (value 7) and q becomes null, so the loop ends. The final list is 2, 1, 4, 3, 6, 5, 7.
Why the last element stays in place: With an odd number of nodes the final node has no partner to swap with, so its value remains unchanged.