Linked List Reversal

What should be added in place of “/*ADD A STATEMENT HERE*/”, so that the function correctly reverses a linked list.

• *head_ref = current;

• *head_ref = prev;

• *head_ref = next;

• *head_ref = NULL;

Answer explanation

*head_ref = prev; At the end of while loop, the prev pointer points to the last node of original linked list.

We need to change *head_ref so that the head pointer now starts pointing to the last node.

What does the following function do for a given Linked List with first node as head?

• Prints all nodes of linked lists

• Prints alternate nodes of Linked List

• Prints all nodes of linked list in reverse order

• Prints alternate nodes in reverse order

Answer explanation

fun1() prints the given Linked List in reverse manner.

How many pointers will be required to perform reversal in linked list?

• 2

• 3

• 1

• 4

Answer explanation

The idea is to use three pointers curr, prev, and next to keep track of nodes to update reverse links.

1. Initialize three pointers prev as NULL, curr as head, and next as NULL.

2. Iterate through the linked list. In a loop, do the following:

3. Before changing the next of curr, store the next node

next = curr -> next

4. Now update the next pointer of curr to the prev

curr -> next = prev

5. Update prev as curr and curr as next

Complete the step 5 with proper code snippet

-------

-------

• prev = curr

  curr = next

• prev=next

  curr=prev

• curr=next

  prev=next

• curr = next

  prev = curr

Answer explanation

prev = curr ;curr = next completes the linked list reversal

What is the time complexity to perform reversal operation in linked list?

• O(1)

• O(n)

• O(logn)

• O(n logn)

Answer explanation

It takes time complexity of O(n) to perform linked list reversal.

While reversing a linked list we initialize the pointer prev,curr,next as

• NULL,head,NULL

• NULL,NULL,head

• NULL,NULL,NULL

• head,head,NULL

Answer explanation

Initialize three pointers prev as NULL, curr as head, and next as NULL.

Which of the following statement is false with respect to reversing a linked list?

• The loop statement while(curr!=NULL) helps in traversing the entire list inorder to reverse the list

• Before changing the next of curr, store the next node as next = curr -> next

• prev=current keeps prev pointer moving ahead of next pointer

• None of the above

Answer explanation

Update prev as curr and curr as next so that prev ->curr->next order is maintained

10. How many approaches are there to reverse a linked list?

• 1

• 2

• 3

• 4

Answer explanation

Linked List can be reversed using one of the following ways

Iterative Method

Recursive Method

By using Stack

Consider the linked list 1->2->3->4

After successful execution of while loop 3 times ,the node 3 points to which of the following node?

• 1

• 2

• 4

• NULL

Answer explanation

After successful execution of while loop 3 times ,the node 3 points to node 2

Which of the above lines from 1-4 can be altered to execute the linked list reversal?

• 1

• 2

• 3

• 4

Answer explanation

current = prev is modified as current=next to execute the linked list reversal