Register

GO Classes DPP | GATE CS | Data Structures | Linked List Reverse Implement

231 views
8 8 votes

Consider the following C-style code fragment for reversing a non-empty singly linked list:

curr = front;
next = curr->next;
prev = NULL;

while (curr != NULL) {
    (*)
}

front = prev;

See the figure to understand what ”reverse” means : 

Which code should replace $\texttt{(*)}$ so that the list is reversed correctly?

  1. next->next = prev;
prev = curr;
curr = next;
if (next != NULL) next = next->next;

  2. curr->next = prev;
prev = curr;
curr = next;
if (next != NULL) next = next->next;
  3. next->next = curr;
prev = curr;
curr = next;
if (next != NULL) next = next->next;

  4. prev = curr;
curr = next;
curr->next = prev;
if (next != NULL) next = next->next;

2 Answers

1 1 vote

At each step, the current node must point backward:

$\texttt{curr->next = prev;}$

Then the three pointers move forward:

prev = curr;
curr = next;
if (next != NULL) next = next->next;

Option B does exactly this. 

The other options either reverse the wrong link or update $\texttt{curr}$ before fixing its $\texttt{next}$.

Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes DPP | GAT...Next → · GO Classes DPP | GAT...
← Previous in category · GO Classes DPP | GAT...Next in category → · GO Classes DPP | GAT...
Position:
Show:

Related questions

6 6 votes
2 2 answers
251
251 views
GO Classes asked Jul 6
251 views
GO Classes DPP | GATE CS | Data Structures | Linked List Reverse
A singly linked list contains $n$ nodes. We want to reverse the order of the elements in the linked list by changing links, not by copying all elements into an array.Whic...
6 6 votes
2 2 answers
210
210 views
GO Classes asked Jul 6
210 views
GO Classes DPP | GATE CS | Data Structures | Linked List Application
The UNIX editor $\texttt{vi}$ allows searching in both directions, and if the search reaches one end, it wraps around and continues from the other end.If the sequence of ...
6 6 votes
3 3 answers
208
208 views
GO Classes asked Jul 6
208 views
GO Classes DPP | GATE CS | Data Structures | Circular Linked List
A circular linked list has $n$ nodes. A function prints every node exactly once and stops when it reaches the starting node again.What is the running time of printing the...
7 7 votes
2 2 answers
232
232 views
GO Classes asked Jul 6
232 views
GO Classes DPP | GATE CS | Data Structures | Final Head After Reversal
The following function is supposed to reverse a singly linked list:struct node { int data; struct node *next; }; static void reverse(struct node head_ref) { struct node ...